//#pragma GCC optimize(2)
#include<algorithm>
#include<stdlib.h>
#include<iostream>
#include<cassert>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<vector>
#include<cstdio>
#include<random>
#include<bitset>
#include<queue>
#include<cmath>
#include<set>
#include<map>
//#include<bits/stdc++.h>
#define uint unsigned int
#define int long long
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define lll __int128
#define db double
#define ld long double
#define pii pair<int,int>
#define For(i,l,r) for(int i=(l);i<=(r);++i)
#define rof(i,r,l) for(int i=(r);i>=(l);--i)
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
#define lowbit(t) (t&-t)
#define ckmax(a,b) a=max(a,b)
#define ckmin(a,b) a=min(a,b)
#define ppct(t) __builtin_popcount(t)
#define x1 xxx111
#define y1 yyy111
#define x2 xxx222
#define y2 yyy222
using namespace std;
const int N=1e5+10,inf=1e18,mod=1e9+7;
struct giao{
    int x,y,val;
}max1,max2,max3;
bool cmp(giao g1,giao g2){
    return g1.x<g2.x;
}
vector<giao>vec;
struct edge{
    int to,len;
};
vector<edge>e[N];
int u[N],v[N],w[N];
int du[N];
int n,m;
void upd(giao t){
    if(t.val>max1.val){
        max3=max2;
        max2=max1;
        max1=t;
    }
    else if(t.val>max2.val){
        max3=max2;
        max2=t;
    }
    else if(t.val>max3.val)
        max3=t;
}
int lth[N];
int ans=-1;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    For(i,1,m){
        cin>>u[i]>>v[i]>>w[i];
        ++du[u[i]];
        ++du[v[i]];
    }
    For(i,1,m){
        if(du[u[i]]>du[v[i]]||(du[u[i]]==du[v[i]]&&u[i]>v[i]))
            e[u[i]].push_back({v[i],w[i]});
        else
            e[v[i]].push_back({u[i],w[i]});
    }
    For(x,1,n){
        max1=max2=max3={0,0,-inf};
        vec.clear();
        for(auto [nxt,len]:e[x])lth[nxt]=len;
        for(auto [y,len1]:e[x])
            for(auto [z,len2]:e[y])
                if(lth[z])vec.push_back({min(y,z),max(y,z),lth[z]+len1+len2});
        for(auto [nxt,len]:e[x])lth[nxt]=0;
        if(vec.empty())continue;
        sort(vec.begin(),vec.end(),cmp);
        int j=0;
        For(i,0,vec.size()-1){
            if(i==vec.size()-1||(vec[i].x!=vec[i+1].x)){
                For(it,j,i){
                    auto [x,y,val]=vec[it];
                    if(max1.y!=x&&max1.y!=y)ckmax(ans,val+max1.val);
                    else if(max2.y!=x&&max2.y!=y)ckmax(ans,val+max2.val);
                    else if(max3.y!=x&&max3.y!=y)ckmax(ans,val+max3.val);
                }
                For(it,j,i){
                    auto [x,y,val]=vec[it];
                    if(max1.y==y){
                        if(val>max1.val)
                            max1={x,y,val};
                    }
                    else if(max2.y==y){
                        if(val>max2.val){
                            max2={x,y,val};
                            if(max2.val>max1.val)swap(max1,max2);
                        }
                    }
                    else if(max3.y==y){
                        if(val>max3.val){
                            max3={x,y,val};
                            if(max3.val>max2.val){
                                swap(max3,max2);
                                if(max2.val>max1.val)
                                    swap(max2,max1);
                            }
                        }
                    }
                    else upd({x,y,val});
                }
                j=i+1;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}
/*
 6 9
 1 2 3
 2 3 1
 3 4 2
 4 5 1
 3 5 7
 2 5 2
 1 5 3
 4 6 2
 5 6 1
 
 6 6
 1 3 2
 1 2 2
 2 3 4
 3 4 1
 3 6 6
 1 4 8
 */