#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define int long long
#define pli pair<ll,int>
#define fi first
#define se second

const int maxn=3e5+5;

inline int read()
{
    int x;
    x=0;bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    flag?x=-x:0;
    return x;
}

struct Edge
{
    int tot;
    int head[maxn];
    struct edgenode{int to,nxt;ll w;}edge[maxn*2];
    inline void add(int x,int y,int z)
    {
        tot++;
        edge[tot].to=y;
        edge[tot].w=z;
        edge[tot].nxt=head[x];
        head[x]=tot;
    }
}G,fG;

int n,m;
int from[maxn],rd[maxn],cd[maxn];

bool vis[maxn],del[maxn];

ll ans=1e18;
ll dis[maxn];

inline void dij(int st)
{
    for(int i=0;i<=n;i++) vis[i]=false,dis[i]=1e18;
    dis[st]=0;
    priority_queue<pli,vector<pli>,greater<pli>>que;
    que.push({0,st});
    while(!que.empty())
    {
        int u=que.top().se;que.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=G.head[u];i;i=G.edge[i].nxt)
        {
            int v=G.edge[i].to;
            if(dis[v]>dis[u]+G.edge[i].w)
            {
                dis[v]=dis[u]+G.edge[i].w;
                que.push({dis[v],v});
            }
        }
    }
}
inline void bfs()
{
    queue<int>que;
    for(int i=1;i<=n;i++) if(!rd[i]||!cd[i]) que.push(i),vis[i]=true;
    while(!que.empty())
    {
        int u=que.front();que.pop();
        if(!rd[u])
            for(int i=G.head[u];i;i=G.edge[i].nxt)
            {
                int v=G.edge[i].to;
                rd[v]--;
                if(!vis[v]&&!rd[v]) que.push(v),vis[v]=true;
            }
        else
            for(int i=fG.head[u];i;i=fG.edge[i].nxt)
            {
                int v=fG.edge[i].to;
                cd[v]--;
                if(!vis[v]&&!cd[v]) que.push(v),vis[v]=true;
            }
    }
}

signed main()
{
    // scanf("%d%d",&n,&m);
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        // scanf("%d%d%d",&u,&v,&w);
        u=read(),v=read(),w=read();
        if(u==v) {ans=min(ans,(ll)w);continue;}
        cd[u]++,rd[v]++;
        G.add(u,v,w);from[v]=G.tot;
        fG.add(v,u,w);
    }
    bfs();
    for(int i=1;i<=n;i++)
    {
        if(cd[i]==1&&rd[i]==1)
        {
            G.edge[from[i]].to=G.edge[G.head[i]].to;
            G.edge[from[i]].w+=G.edge[G.head[i]].w;
            from[G.edge[G.head[i]].to]=from[i];
            del[i]=true;
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(rd[i]&&cd[i]&&!del[i])
        {
            cnt++;
            assert(cnt<=4000);
            dij(i);
            for(int u=1;u<=n;u++) if(dis[u]^dis[0]) for(int j=G.head[u];j;j=G.edge[j].nxt)
            {
                int v=G.edge[j].to;
                if(v==i) ans=min(ans,dis[u]+G.edge[j].w);
            }
        }
    }
    printf("%lld",ans==dis[0]?-1:ans);
}