#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;

template<typename type>
inline void read(type &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;
}

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=0;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);
    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;
    }
    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);
}

answer.code: In function ‘int main()’:
answer.code:69:11: error: no matching function for call to ‘read()’
   69 |     n=read(),m=read();
      |       ~~~~^~
answer.code:12:13: note: candidate: ‘template<class type> void read(type&)’
   12 | inline void read(type &x)
      |             ^~~~
answer.code:12:13: note:   template argument deduction/substitution failed:
answer.code:69:11: note:   candidate expects 1 argument, 0 provided
   69 |     n=read(),m=read();
      |       ~~~~^~
answer.code:69:20: error: no matching function for call to ‘read()’
   69 |     n=read(),m=read();
      |                ~~~~^~
answer.code:12:13: note: candidate: ‘template<class type> void read(type&)’
   12 | inline void read(type &x)
      |             ^~~~
answer.code:12:13: note:   template argument deduction/substitution failed:
answer.code:69:20: note:   candidate expects 1 argument, 0 provided
   69 |     n=read(),m=read();
      |                ~~~~^~
answer.code:74:15: error: no matching function for call to ‘read()’
   74 |         u=read(),v=read(),w=read();
      |           ~~~~^~
answer.code:12:13: note: candidate: ‘template<class type> void read(type&)’
   12 | inline void read(type &x)
      |             ^~~~
answer.code:12:13: note:   template argument deduction/substitution failed:
answer.code:74:15: note:   candidate expects 1 argument, 0 provided
   74 |         u=read(),v=read(),w=read();
      |           ~~~~^~
answer.code:74:24: error: no matching function for call to ‘read()’
   74 |         u=read(),v=read(),w=read();
      |                    ~~~~^~
answer.code:12:13: note: candidate: ‘template<class type> void read(type&)’
   12 | inline void read(type &x)
      |             ^~~~
answer.code:12:13: note:   template argument deduction/substitution failed:
answer.code:74:24: note:   candidate expects 1 argument, 0 provided
   74 |         u=read(),v=read(),w=read();
      |                    ~~~~^~
answer.code:74:33: error: no matching function for call to ‘read()’
   74 |         u=read(),v=read(),w=read();
      |                             ~~~~^~
answer.code:12:13: note: candidate: ‘template<class type> void read(type&)’
   12 | inline void read(type &x)
      |             ^~~~
answer.code:12:13: note:   template argument deduction/substitution failed:
answer.code:74:33: note:   candidate expects 1 argument, 0 provided
   74 |         u=read(),v=read(),w=read();
      |                             ~~~~^~