#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 = 0x3f3f3f3f3f3f3f3f, 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();
}
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 i = 1;i <= n;i++)if(!book2[i]){
    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(i);dfs(i,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;dis[j] = INF;}
        while(!que.empty())que.pop();
        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;
            for(auto i : edg2[u]){
                total++;
                int v = i.first, w = i.second;
                // cerr << " v = " << v << endl;
                if(dis[v] > dis[u] + w){
                    dis[v] = dis[u] + w;
                    que.push(make_pair(dis[v],make_pair(v,0)));
                }
            }
        }
        for(int i = 1;i <= cnt;i++){dist[S][i] = dis[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]]);
    }
}
    // 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
*/#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 = 0x3f3f3f3f3f3f3f3f, maxp = 4e3 + 10;
int n, m;

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

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;
        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)));
            }
        }
    }
}
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;
    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]){
            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;
}

int id[maxn], rev[maxn];
int dist[maxp][maxp];

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, w = i.second;dfs2(v, u);}
    if(id[u])vec.pop_back();
}

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;
    for(int i = 1;i <= n;i++)if(dis[i] == INF){dijsktra(i);dfs(i,0);}
    memset(dist,0x3f,sizeof(dist));int cnt = 0;
    for(auto i : ed){
        int u = i.second.first, v = i.second.second, w = i.first;
        if(!id[u]){id[u] = ++cnt;rev[id[u]] = u;}
        if(!id[v]){id[v] = ++cnt;rev[id[v]] = v;}
        dist[id[u]][id[v]] = w;
    }
    memset(book,0,sizeof(book));
    for(int i = 1;i <= n;i++){if(!book[i])dfs2(i,i);}
    int total = 0;
    for(int S = 1;S <= cnt;S++){
        for(int j = 1;j <= cnt;j++){book[j] = 0;dis[j] = INF;}
        while(!que.empty())que.pop();
        que.push(make_pair(0,make_pair(S,0)));dis[S] = 0;
        while(!que.empty()){
            total++;
            auto tmp = que.top();
            int u = tmp.second.first;que.pop();
            if(book[u])continue;book[u] = 1;
            for(int v = 1;v <= cnt;v++){
                if(v == u)continue;int w = dist[u][v];
                // cerr << " v = " << v << endl;
                if(w != INF && dis[v] > dis[u] + w){
                    dis[v] = dis[u] + w;
                    que.push(make_pair(dis[v],make_pair(v,0)));
                }
            }
        }
        for(int i = 1;i <= cnt;i++){dist[S][i] = dis[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]]);
    }
    printf("%lld\n",ans == INF ? -1 : ans);
    return;
}
};
bool edmemory;
signed main(){
    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
*/

answer.code:160:6: error: redefinition of ‘bool stmemory’
  160 | bool stmemory;
      |      ^~~~~~~~
answer.code:4:6: note: ‘bool stmemory’ previously declared here
    4 | bool stmemory;
      |      ^~~~~~~~
answer.code:162:12: error: redefinition of ‘long long int Call_me_Eric::read()’
  162 | inline int read(){
      |            ^~~~
answer.code:6:12: note: ‘long long int Call_me_Eric::read()’ previously defined here
    6 | inline int read(){
      |            ^~~~
answer.code:168:11: error: redefinition of ‘const long long int Call_me_Eric::maxn’
  168 | const int maxn = 4e5 + 10, INF = 0x3f3f3f3f3f3f3f3f, maxp = 4e3 + 10;
      |           ^~~~
answer.code:12:11: note: ‘const long long int Call_me_Eric::maxn’ previously defined here
   12 | const int maxn = 4e5 + 10, INF = 0x3f3f3f3f3f3f3f3f, maxp = 5e3 + 10;
      |           ^~~~
answer.code:168:28: error: redefinition of ‘const long long int Call_me_Eric::INF’
  168 | const int maxn = 4e5 + 10, INF = 0x3f3f3f3f3f3f3f3f, maxp = 4e3 + 10;
      |                            ^~~
answer.code:12:28: note: ‘const long long int Call_me_Eric::INF’ previously defined here
   12 | const int maxn = 4e5 + 10, INF = 0x3f3f3f3f3f3f3f3f, maxp = 5e3 + 10;
      |                            ^~~
answer.code:168:54: error: redefinition of ‘const long long int Call_me_Eric::maxp’
  168 | const int maxn = 4e5 + 10, INF = 0x3f3f3f3f3f3f3f3f, maxp = 4e3 + 10;
      |                                                      ^~~~
answer.code:12:54: note: ‘const long long int Call_me_Eric::maxp’ previously defined here
   12 | const int maxn = 4e5 + 10, INF = 0x3f3f3f3f3f3f3f3f, maxp = 5e3 + 10;
      |                                                      ^~~~
answer.code:169:5: error: redefinition of ‘long long int Call_me_Eric::n’
  169 | int n, m;
      |     ^
answer.code:13:5: note: ‘long long int Call_me_Eric::n’ previously declared here
   13 | int n, m;
      |     ^
answer.code:169:8: error: redefinition of ‘long long int Call_me_Eric::m’
  169 | int n, m;
      |        ^
answer.code:13:8: note: ‘long long int Call_me_Eric::m’ previously declared here
   13 | int n, m;
      |        ^
answer.code:171:5: error: redefinition of ‘long long int Call_me_Eric::head [400010]’
  171 | int head[maxn], tot;
      |     ^~~~
answer.code:16:5: note: ‘long long int Call_me_Eric::head [400010]’ previously declared here
   16 | int head[maxn], tot;
      |     ^~~~
answer.code:171:17: error: redefinition of ‘long long int Call_me_Eric::tot’
  171 | int head[maxn], tot;
      |                 ^~~
answer.code:16:17: note: ‘long long int Call_me_Eric::tot’ previously declared here
   16 | int head[maxn], tot;
      |                 ^~~
answer.code:172:8: error: redefinition of ‘struct Call_me_Eric::edge’
  172 | struct edge{
      |        ^~~~
answer.code:17:8: note: previous definition of ‘struct Call_me_Eric::edge’
   17 | struct edge{
      |        ^~~~
answer.code:175:2: error: conflicting declaration ‘int Call_me_Eric::e [800020]’
  175 | }e[maxn << 1];
      |  ^
answer.code:20:2: note: previous declaration as ‘Call_me_Eric::edge Call_me_Eric::e [800020]’
   20 | }e[maxn << 1];
      |  ^
answer.code:176:6: error: redefinition of ‘void Call_me_Eric::add(long long int, long long int, long long int)’
  176 | void add(int u,int v,int w){e[++tot] = edge(v,head[u],w);head[u] = tot;}
      |      ^~~
answer.code:21:6: note: ‘void Call_me_Eric::add(long long int, long long int, long long int)’ previously defined here
   21 | void add(int u,int v,int w){e[++tot] = edge(v,head[u],w);head[u] = tot;}
      |      ^~~
answer.code:179:47: error: redefinition of ‘std::priority_queue<std::pair<long long int, std::pair<long long int, long long int> >, std::vector<std::pair<long long int, std::pair<long long int, long long int> > >, std::greater<std::pair<long long int, std::pair<long long int, long long int> > > > Call_me_Eric::que’
  179 | priority_queue<pii,vector<pii>,greater<pii> > que;
      |                                               ^~~
answer.code:24:47: note: ‘std::priority_queue<std::pair<long long int, std::pair<long long int, long long int> >, std::vector<std::pair<long long int, std::pair<long long int, long long int> > >, std::greater<std::pair<long long int, std::pair<long long int, long long int> > > > Call_me_Eric::que’ previously declared here
   24 | priority_queue<pii,vector<pii>,greater<pii> > que;
      |                                               ^~~
answer.code:180:5: error: redefinition of ‘long long int Call_me_Eric::dis [400010]’
  180 | int dis[maxn], pre[maxn];bool book[maxn];
      |     ^~~
answer.code:25:5: note: ‘long long int Call_me_Eric::dis [400010]’ previously declared here
   25 | int dis[maxn], pre[maxn];bool book[maxn];vector<int> st;
      |     ^~~
answer.code:180:16: error: redefinition of ‘long long int Call_me_Eric::pre [400010]’
  180 | int dis[maxn], pre[maxn];bool book[maxn];
      |                ^~~
answer.code:25:16: note: ‘lon...