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

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

const int maxn=3e5+5;

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;

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=1;i<=n;i++) vis[i]=false,dis[i]=1e15;
    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});
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        if(u==v) {ans=min(ans,(ll)w);continue;}
        cd[u]++,rd[v]++;
        G.add(u,v,w);from[v]=G.tot;
    }
    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;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(rd[i]&&cd[i]&&!del[i])
        {
            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==1e18?-1:ans);
}