#include<bits/stdc++.h>
using namespace std;
const int N=100005,INF=1e9;
int ind[N];
pair<int,int>tag[N];
vector<pair<int,int>>e[N];
vector<pair<int, tuple<int,int,int>>> ring;
vector<int> res[N];
// vector<tuple<int,int,int>>res[N];
int ord(int x,int v){
    return (ind[x]>ind[v]||(ind[x]==ind[v]&&x>v));
}
int CNT[N];
void report(int x,int y,int z,int val){
  //  cout<<x<<" "<<y<<" "<<z<<" "<<val<<endl;
    // if(y>z)res[x].push_back({y,z,val});
    // else res[x].push_back({z,y,val});
    // if(x>z)res[y].push_back({x,z,val});
    // else res[y].push_back({z,x,val});
    // if(x>y)res[z].push_back({x,y,val});
    // else res[z].push_back({y,x,val});
    if(CNT[x]<5||CNT[y]<5||CNT[z]<5) {
        ring.push_back({-val, {x, y, z}});
        ++CNT[x]; ++CNT[y]; ++CNT[z];
    }
}
void dfs2(int x){
    for(auto [v,val]:e[x]){
        if(!ord(x,v))continue;
        tag[v]={x,val};
    }
    for(auto [v,val]:e[x]){
        if(!ord(x,v))continue;
        for(auto [v2,val2]:e[v]){
            if(!ord(v,v2))continue;
            if(tag[v2].first==x){
                report(x,v,v2,tag[v2].second+val+val2);
            }
        }
    }
}
int cnt[N];
int solve(int x) {
    vector<tuple<int,int,int>> ri;
    int now=0;
    for(auto &id : res[x]) {
        auto [xx, yy, zz] = ring[id].second;
        if(yy == x) swap(xx, yy);
        if(zz == x) swap(zz, xx);
        if(cnt[yy] < 3 || cnt[zz] < 3) {
            ++cnt[yy];
            ++cnt[zz];
            ri.push_back({yy, zz, -ring[id].first});
            ++now;
        }
        if(now >= 6) break;
    }
    int ans = -1;
    for(int i = 0; i < ri.size(); ++i) {
        for(int j = i+1; j < ri.size(); ++j) {
            auto [xi, yi, vali] = ri[i];
            auto [xj, yj, valj] = ri[j];
            if(xi!=xj&&yi!=xj&&xi!=yj&&yi!=yj)
                ans=max(ans, vali+valj);
        }
    }
    for(auto [xx, yy, val] : ri) --cnt[xx], --cnt[yy];
    return ans;
}
// int solve(int x){
//     if(res[x].size()<=1)return -1;
//     int max_v=-1;
//     vector<pair<int,int>>s;
//     for(auto [y,z,val]:res[x]){
//         if(val>max_v){
//             max_v=val;
//         }
//     }
//     int ans=-1;
//     for(auto [y,z,val]:res[x]){
//         if(val==max_v){
//             s.push_back({y,z});
//         }
//     }
//     for(auto [max_y,max_z]:s){
//         pair<int,int> fix_y={-INF,-1},sfix_y={-INF,-1},fix_z={-INF,-1},sfix_z={-INF,-1};
//         int libre=-1;
//         for(auto [y,z,val]:res[x]){
//             if(max_y==y){
//                 if(max_z!=z){
//                     if(val>=fix_y.first){
//                         sfix_y=fix_y;
//                         fix_y={val,z};
//                     }
//                     else sfix_y=max(sfix_y,{val,z});
//                 }
//             }
//             else if(max_z==z){
//                 if(max_y!=y){
//                     if(val>=fix_z.first){
//                         sfix_z=fix_z;
//                         fix_z={val,y};
//                     }
//                     else sfix_z=max(sfix_z,{val,y});
//                 }
//             }
//             else if(max_z==y){
//                 if(max_y!=z){
//                     if(val>=fix_z.first){
//                         sfix_z=fix_z;
//                         fix_z={val,z};
//                     }
//                     else sfix_z=max(sfix_z,{val,z});
//                 }
//             }
//             else if(max_y==z){
//                 if(max_z!=y){
//                     if(val>=fix_y.first){
//                         sfix_y=fix_y;
//                         fix_y={val,y};
//                     }
//                     else sfix_y=max(sfix_y,{val,y});
//                 }
//             }
//             else {
//         //     cout<<"safe "<<y<<" "<<z<<endl;
//                 libre=max(libre,val);}
//         }
//     // cout<<x<<" "<<max_v<<" "<<max_y<<" "<<max_z<<' '<<fix_y.second<<" "<<fix_z.second<<" "<<sfix_y.second<<" "<<sfix_z.second<<" "<<libre<<endl;
//         if(libre!=-1)ans=max(ans,max_v+libre);
//         if(fix_y.second!=fix_z.second)ans=max(ans,fix_y.first+fix_z.first);
//         if(sfix_y.second!=fix_z.second)ans=max(ans,sfix_y.first+fix_z.first);
//         if(fix_y.second!=sfix_z.second)ans=max(ans,fix_y.first+sfix_z.first);
//         if(ans==max_v*2)return ans;
//     }
//   /////  cout<<ans<<endl;
//     return ans;
// }
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        e[x].push_back({y,z});
        e[y].push_back({x,z});
        ind[x]++;
        ind[y]++;
    }
    for(int i=1;i<=n;i++){
        dfs2(i);
    }
    sort(ring.begin(), ring.end());
    int now = 0;
    for(auto &[val, o] : ring) {
        auto [x, y, z] = o;
        res[x].push_back(now);
        res[y].push_back(now);
        res[z].push_back(now++);
    }
    int ans=-1;
    for(int i=1;i<=n;i++){
        ans=max(ans,solve(i));
    }
    printf("%d\n",ans);

}