#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
#define int long long
const int inf=1e15;
map<int,int> ve1[maxn],ve2[maxn];
int ans=inf;
void add(int x,int y,int w){
    if(x==y){
        ans=min(ans,w);return;
    }
    if(ve1[x].find(y)==ve1[x].end())ve1[x][y]=w;
    else ve1[x][y]=min(ve1[x][y],w);
    if(ve2[y].find(x)==ve2[y].end())ve2[y][x]=w;
    else ve2[y][x]=min(ve2[y][x],w);
}
struct kkk{
    int x,len;
    bool operator<(kkk k1)const{
        return len>k1.len;
    }
};
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    while(m--){
        int x,y,w;cin>>x>>y>>w;
        add(x,y,w);
    }
    vector<int> vis(n+1,0);
    queue<int> qu;
    auto ok = [&](int x){
        // cout<<"x="<<x<<"\n";
        if(vis[x]==0&&(ve1[x].empty()||ve2[x].empty()||(ve1[x].size()==1&&ve2[x].size()==1))){
            vis[x]=1;
            qu.push(x);
            return true;
        }
        return false;
    };
    for(int i=1;i<=n;i++)ok(i);
    while(!qu.empty()){
        int x=qu.front();qu.pop();
        // cout<<"qu x="<<x<<"\n";
        if(ve1[x].empty()){
            for(auto [y,w]:ve2[x]){
                ve1[y].erase(x);
                ok(y);
            }
            ve2[x].clear();
        }
        if(ve2[x].empty()){
            for(auto [y,w]:ve1[x])ve2[y].erase(x),ok(y);
            ve1[x].clear();
        }
        if(ve1[x].size()==1&&ve2[x].size()==1){
            add(ve2[x].begin()->first,ve1[x].begin()->first,ve1[x].begin()->second+ve2[x].begin()->second);
            ok(ve1[x].begin()->first);
            ok(ve2[x].begin()->first);
            ve1[x].clear();
            ve2[x].clear();
        }
    }
    int tot=0;
    vector<int> lis;
    for(int i=1;i<=n;i++)if(!ve1[i].empty()||!ve2[i].empty()){
        assert(!ve1[i].empty()&&!ve2[i].empty());
        lis.push_back(i);
        tot++;
    }
    auto getid = [&](int x){
        return lower_bound(lis.begin(),lis.end(),x)-lis.begin()+1;
    };
    vector<vector<pair<int,int>>> v1(tot+1),v2(tot+1);
    for(int i=1;i<=n;i++)if(!ve1[i].empty()){
        int id=getid(i);
        v1[id]=vector<pair<int,int>>(ve1[i].begin(),ve1[i].end());
        v2[id]=vector<pair<int,int>>(ve2[i].begin(),ve2[i].end());
        for(auto &[x,y]:v1[id])x=getid(x);
        for(auto &[x,y]:v2[id])x=getid(x);
    }
    auto solve = [&](int root){
        vector<int> dis1(tot+1,inf),dis2(tot+1,inf);
        priority_queue<kkk,vector<kkk>> qu;
        qu.push(kkk{root,0});
        while(!qu.empty()){
            kkk k1=qu.top();qu.pop();
            if(dis1[k1.x]>k1.len){
                dis1[k1.x]=k1.len;
            }
            else continue;
            for(auto [to,w]:v1[k1.x])if(dis1[to]==inf){
                qu.push(kkk{to,w+k1.len});
            }
        }
        qu.push(kkk{root,0});
        while(!qu.empty()){
            kkk k1=qu.top();qu.pop();
            if(dis2[k1.x]>k1.len){
                dis2[k1.x]=k1.len;
            }
            else continue;
            for(auto [to,w]:v2[k1.x])if(dis2[to]==inf){
                qu.push(kkk{to,w+k1.len});
            }
        }
        for(int i=1;i<=tot;i++)if(i!=root)ans=min(ans,dis1[i]+dis2[i]);
    };
    for(int i=1;i<=tot;i++)solve(i);
    if(ans==inf)cout<<-1;
    else cout<<ans<<"\n";
}