#include<bits/stdc++.h>
#define int long long
using namespace std;
bool stmemory;
namespace Call_me_Eric{
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 4e5 + 10, INF = 0x3f3f3f3f3f3f3f, maxp = 5e3 + 10;
int n, m;
bool book2[maxn];

int head[maxn], tot;
struct edge{
    int to, nexte, wei;
    edge(int to = 0,int ne = 0,int we = 0):to(to),nexte(ne),wei(we){}
}e[maxn << 1];
void add(int u,int v,int w){e[++tot] = edge(v,head[u],w);head[u] = tot;}

typedef pair<int,pair<int,int> > pii;
priority_queue<pii,vector<pii>,greater<pii> > que;
int dis[maxn], pre[maxn];bool book[maxn];vector<int> st;

void dijsktra(int S){
    que.push(make_pair(0,make_pair(S,0)));dis[S] = 0;
    while(!que.empty()){
        auto tmp = que.top();
        int u = tmp.second.first;que.pop();
        if(book[u])continue;book[u] = 1;pre[u] = tmp.second.second;
        if(book2[u])continue;book2[u] = 1;st.push_back(u);
        for(int i = head[u];i;i = e[i].nexte){
            int v = e[i].to, w = e[i].wei;
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                que.push(make_pair(dis[v],make_pair(v,i)));
            }
        }
    }
}
int dfn[maxn], low[maxn], idx;
vector<pii> ed;bool anc[maxn];
vector<pair<int,int> > tre[maxn];
int ans = INF;
int dep[maxn];
void dfs(int u,int f){
    anc[u] = 1;dfn[u] = low[u] = ++idx;
    for(int i = head[u];i;i = e[i].nexte){
        int v = e[i].to, w = e[i].wei;
        if(dis[v] == dis[u] + w && pre[v] == i && !dep[v] && book2[v]){
            dep[v] = dep[u] + 1;
            tre[u].push_back(make_pair(v, w));
            dfs(v, u);
        }
        else{
            if(anc[v]){ans = min(ans,w + dis[u] - dis[v]);}
            else{ed.push_back(make_pair(w,make_pair(u, v)));}
        }
    }
    anc[u] = 0;low[u] = idx;
}

int id[maxn];
int dist[maxp][maxp];
vector<pair<int,int> > edg2[maxn];

vector<int> vec;
void dfs2(int u,int f){
    book[u] = 1;
    if(id[u]){
        for(int i : vec){dist[id[i]][id[u]] = dis[u] - dis[i];}
        vec.push_back(u);
    }
    for(auto i : tre[u]){int v = i.first;dfs2(v, u);}
    if(id[u])vec.pop_back();
}
int dis1[maxn];
void main(){
    n = read(); m = read();int u, v, w;
    for(int i = 1;i <= m;i++){
        u = read(); v = read(); w = read();
        add(u, v, w);
    }
    for(int i = 1;i <= n;i++)dis[i] = INF,book[i] = 0;
    int cnt = 0;
    int total = 0;
    memset(dist,0x3f,sizeof(dist));
for(int t = 1;t <= n;t++)if(!book2[t]){
    for(int i = 1;i <= cnt;i++){edg2[i].clear();for(int j = 1;j <= cnt;j++)dist[i][j] = INF;}
    for(int i : st)id[i] = 0;
    cnt = 0;st.clear();ed.clear();
    dijsktra(t);dfs(t,0);
    for(auto i : ed){
        int u = i.second.first, v = i.second.second, w = i.first;
        if((dfn[u] <= dfn[v] && dfn[v] <= low[u]))continue;
        if(!id[u]){id[u] = ++cnt;}
        if(!id[v]){id[v] = ++cnt;}
        dist[id[u]][id[v]] = w;
    }
    // cerr << "cnt = " << cnt << " st = " << st.size() << " ed = " << ed.size() << endl;
    for(int i : st)book[i] = 0;
    for(int i : st){if(!book[i])dfs2(i,i);}
    int totall = 0;
    for(int i = 1;i <= cnt;i++)for(int j = 1;j <= cnt;j++)
        if(dist[i][j] != INF){edg2[i].push_back(make_pair(j,dist[i][j]));totall++;}
        // cerr << "totall = " << totall << endl;
    // cerr << "111111111111111\n";
    for(int S = 1;S <= cnt;S++){
        for(int j = 1;j <= cnt;j++){book[j] = 0;dis1[j] = INF;}
        while(!que.empty())que.pop();
        que.push(make_pair(0,make_pair(S,0)));dis1[S] = 0;
        while(!que.empty()){
            auto tmp = que.top();
            int u = tmp.second.first;que.pop();
            if(book[u])continue;book[u] = 1;
            for(auto i : edg2[u]){
                total++;
                int v = i.first, w = i.second;
                // cerr << " v = " << v << endl;
                if(dis1[v] > dis1[u] + w){
                    dis1[v] = dis1[u] + w;
                    que.push(make_pair(dis1[v],make_pair(v,0)));
                }
            }
        }
        for(int i = 1;i <= cnt;i++){dist[S][i] = dis1[i];}
    }
    for(auto i : ed){
        int u = i.second.first, v = i.second.second, w = i.first;
        ans = min(ans,w + dist[id[v]][id[u]]);
    }
    // if(ans < 0){ cerr << "S = " << t << " ans = " << ans;break;}
}
    // cerr << "total = " << total << endl;
    printf("%lld\n",ans == INF ? -1 : ans);
    return;
}
};
bool edmemory;
signed main(){
    // freopen("tmp.in","r",stdin);
    auto stclock = clock();
    Call_me_Eric::main();
    auto edclock = clock();
    cerr << (&stmemory - &edmemory) / 1024.0 / 1024.0 << " Mib cost.\n";
    cerr << (edclock - stclock) * 1.0 / CLOCKS_PER_SEC << " Sec cost.\n";
    return 0;
}
/*
5 6
1 2 1
1 4 1
2 3 1
4 5 1
3 4 5
5 2 5
*/