# include<cstdio>
# include<cstring>
# include<queue>
# include<algorithm>
using namespace std;
const int INF=999999999;
const int N=2000;
const int M=600000;
int n,m,e=1,Max=-1;
int fist[N],next[M],u[M],v[M],w[M],vis[N],dis[N],pre[N];
typedef pair<int,int>pii;
void dijkstra(int s,int start,int end){
    priority_queue<pii,vector<pii>,greater<pii> >q;
    for(int i=1;i<=n;i++)if(i==s)dis[i]=0;else dis[i]=INF;
    memset(vis,0,sizeof(vis));
    q.push(make_pair(dis[s],s));
    while(!q.empty()){
        pii p=q.top();q.pop();
        int k=p.second;
        if(vis[k])continue;
        vis[k]=true;
        for(int i=fist[k];i!=-1;i=next[i]){
        if(dis[v[i]]>dis[k]+w[i])
        dis[v[i]]=dis[pre[v[i]]=k]+w[i];
        q.push(make_pair(dis[v[i]],v[i]));
        }
    }
}
void dijkstra_other(int s,int start,int end){
    priority_queue<pii,vector<pii>,greater<pii> >q;
    for(int i=1;i<=n;i++)if(i==s)dis[i]=0;else dis[i]=INF;
    memset(vis,0,sizeof(vis));
    q.push(make_pair(dis[s],s));
    while(!q.empty()){
        pii p=q.top();q.pop();
        int k=p.second;
        if(vis[k])continue;
        vis[k]=true;
        for(int i=fist[k];i!=-1;i=next[i]){
        if((u[i]==start&&v[i]==end)||(u[i]==end&&v[i]==start))continue;
        if(dis[v[i]]>dis[k]+w[i])
        dis[v[i]]=dis[k]+w[i];
        q.push(make_pair(dis[v[i]],v[i]));
        }
    }
}
void built(int a,int b,int c){
    u[e]=a,v[e]=b,w[e]=c;
    next[e]=fist[u[e]];
    fist[u[e]]=e++;
}
void init(){
    memset(fist,-1,sizeof(fist));
    int a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        built(a,b,c);
        built(b,a,c);
    }
}
void solve(){
    dijkstra(1,-1,-1);
    for(int i=n;i!=0;i=pre[i]){
    dijkstra_other(1,pre[i],i);
    Max=max(Max,dis[n]);
    }
}
void print(){
    printf("%d",Max);
}
int main(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    init();
    solve();
    print();
    return 0;
}

测试点 #1：通过该测试点。 得分10，耗时0ms，内存1957kB。 测试点 #2：通过该测试点。 得分10，耗时0ms，内存1957kB。

测试点 #3：通过该测试点。 得分10，耗时0ms，内存1961kB。

测试点 #4：通过该测试点。 得分10，耗时0ms，内存1970kB。

测试点 #5：通过该测试点。 得分10，耗时0ms，内存1982kB。

测试点 #6：通过该测试点。 得分10，耗时15ms，内存2150kB。

测试点 #7：通过该测试点。 得分10，耗时46ms，内存2117kB。

测试点 #8：通过该测试点。 得分10，耗时109ms，内存2105kB。

测试点 #9：超过时间限制。 得分0，耗时1014ms，内存12689kB。

测试点 #10：通过该测试点。 得分10，耗时561ms，内存2265kB。