#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int N=1e6+10;

ll n,m,k;

vector<PII> e[N];
// vector<PII> v;

vector<array<int,3>> ed;
vector<array<int,3>> unused;
int p[N];


int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

ll d1[N][2],d2[N][2];


void dfs1(int x,int fa){
    for(auto [j,w]:e[x]){
      if(j==fa) continue;
      // d1[j]=max(d1[x],w);
      if(w>d1[j][0]){
        d1[j][1]=d1[j][0];
        d1[j][0]=w;
      }else if(w>d1[j][1]){
        d1[j][1]=w;
      }
      dfs1(j,x);
    }
}

void dfs2(int x,int fa){
    for(auto [j,w]:e[x]){
      if(j==fa) continue;
      if(w>d2[j][0]){
        d2[j][1]=d2[j][0];
        d2[j][0]=w;
      }else if(w>d2[j][1]){
        d2[j][1]=w;
      }
      dfs2(j,x);
    }
}
int ans=1e9;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
      int u,v,w;
      cin>>u>>v>>w;
      ed.push_back({w,u,v});
    }
    sort(ed.begin(),ed.end());
    for(int i=1;i<=n;i++) p[i]=i;
    for(auto [w,u,v]:ed){
        if(find(u)!=find(v)){
          p[find(u)]=find(v);
          e[u].push_back({v,w});
          e[v].push_back({u,w});
        }else{
          unused.push_back({w,u,v});
        }
    }
    dfs1(1,-1);
    dfs2(n,-1);
    ans=d1[n][0]+d1[n][1];
    for(auto [w,u,v]:unused){
      vector<int> xx;
      xx.push_back(w);
      xx.push_back(d1[u][0]);
      xx.push_back(d1[u][1]);
      xx.push_back(d2[v][0]);
      xx.push_back(d2[v][1]);
      sort(xx.begin(),xx.end(),greater<int>());
      ans=min(ans,xx[0]+xx[1]);
      xx.clear();
      
      xx.push_back(w);
      xx.push_back(d2[u][0]);
      xx.push_back(d2[u][1]);
      xx.push_back(d1[v][0]);
      xx.push_back(d1[v][1]);
      sort(xx.begin(),xx.end(),greater<int>());
      ans=min(ans,xx[0]+xx[1]);
    }
    cout<<ans<<endl;
}