#include<bits/stdc++.h>
using namespace std;
using i64=long long;
#define all(x) x.begin(),x.end()
#define int long long
void solve(){
    //有向图
    int n;cin>>n;
    int m;cin>>m;
    vector<int>live(n,1);
    vector<map<int,int>>e1(n),e2(n);
    vector<map<int,int>>e(n);
    i64 ans=1e18;
    for(int i=0;i<m;i++){
        int u,v,w;cin>>u>>v>>w;
        u--,v--;
        if(u==v){ans=min(ans,w);continue;}
        if(!e1[u].count(v))e1[u][v]=w;
        else e1[u][v]=min(e1[u][v],w);

        if(!e2[v].count(u))e2[v][u]=w;
        else e2[v][u]=min(e2[v][u],w);
    }
    auto check=[&](int u){
        if(e1.empty()||e2.empty()||e1.size()+e2.size()<=2)return true;
        return false;
    };
    queue<int>q;
    for(int i=0;i<n;i++){
        if(check(i))q.push(i),live[i]=0;
    }
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(auto y:e1[x])e2[y.first].erase(x);
        for(auto y:e2[x])e1[y.first].erase(x);
        for(auto y:e1[x])if(e2[x].count(y.first))ans=min(ans,e2[x][y.first]+y.second);
        //合并u->x->v,u->v
        for(auto [y1,w1]:e2[x]){
            for(auto [y2,w2]:e1[x]){
                if(!e1[y1].count(w2))e1[y1][y1]=w1+w2;
                else e1[y1][y2]=min(e1[y1][y2],w1+w2);
            
                if(!e2[y2].count(y1))e2[y2][y1]=w1+w2;
                else e2[y2][y1]=min(e2[y2][y1],w1+w2);
            }
        }
        for(auto y:e1[x])if(live[y.first]&&check(y.first))q.push(y.first),live[y.first]=0;
        for(auto y:e2[x])if(live[y.first]&&check(y.first))q.push(y.first),live[y.first]=0;
    }
    for(int i=0;i<n;i++){
        if(!live[i])e1[i].clear();
    }
    for(int i=0;i<n;i++){
        if(!live[i])continue;
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>q;
        q.push({0,i});
        vector<i64>dis(n,1e18);
        dis[i]=0;
        while(!q.empty()){
            auto [d,x]=q.top();
            q.pop();
            if(d>dis[x])continue;
            for(auto [y,w]:e1[x]){
                ans=min(dis[x]+dis[y]+w,ans);
                if(dis[y]>dis[x]+w){
                    dis[y]=dis[x]+w;
                    q.push({dis[y],y});
                }
            }
        }
    }
    i64 inf=1e18;
    if(ans==inf)ans=-1;
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T=1;
    while(T--)solve();
}