/*
现场代码，枚举每条边删除
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define mx 1005 using namespace std;
struct orz
{
int d,p;
friend bool operator <(orz a,orz b) {return a.d>b.d;}
};
struct Edge{
int to;
int w;
int id;
};
priority_queue < orz > ss;
int flag,cnt,v[mx],d[mx],n,m,l;
vector<Edge> edge[mx];
bool vis[mx];
void input(){
cin>>n>>l;
int u,v,wei;
Edge test;
for(int i = ;i <= l;i++){
cin>>u>>v>>wei;
if(u == v) continue;
test.id = ++cnt;
test.to = v;
test.w = wei;
edge[u].push_back(test);
test.to = u;
edge[v].push_back(test);
}
m = ;
}
void dij(int s)
{
for(int i = ;i < mx;i++) d[i] = ;
d[s]=;
orz tmp;
tmp.d=,tmp.p=s;
ss.push(tmp);
flag++;
int x,dd;
Edge j;
while (!ss.empty())
{
tmp=ss.top();
ss.pop();
x=tmp.p,dd=tmp.d;
if (v[x]==flag) continue;
v[x]=flag;
for (int i = ;i < edge[x].size();i++){
if(vis[edge[x][i].id]) continue;
j = edge[x][i];
if (d[j.to]>dd+j.w)
{
d[j.to]=dd+j.w;
tmp.d=dd+j.w,tmp.p=j.to;
ss.push(tmp);
}
} }
}
int main(){
freopen("di.in","r",stdin);
freopen("di.out","w",stdout);
input();
int ans = ;
for(int i = ;i <= cnt;i++){
vis[i] = true;
dij();
vis[i] = false;
if(d[n] < ) ans = max(ans,d[n]);
}
cout<<ans;
return ;
}
/*
要使最短路改变，就只能删除最短路经过的边
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm> using namespace std; const int maxn=;
const int maxm=; int n,m,en,f[maxn],q[maxn],dist[maxn],edg[maxm][],z[maxn]; bool use[maxn]; struct edge
{
int e,d,id;
edge *next;
}*v[maxn],ed[maxm<<],*fe[maxn]; void add_edge(int id,int s,int e,int d)
{
en++;
ed[en].next=v[s];v[s]=ed+en;v[s]->e=e;v[s]->d=d;v[s]->id=id;
} void spfa()
{
int front=,tail=;
memset(dist,0x3f,sizeof(dist));
dist[]=;
use[]=true;
q[]=;
for (;front!=tail;)
{
int now=q[front++];
if (front==maxn) front=;
use[now]=false;
for (edge *e=v[now];e;e=e->next)
if (dist[e->e]>dist[now]+e->d)
{
dist[e->e]=dist[now]+e->d;
f[e->e]=now;fe[e->e]=e;
if (!use[e->e])
{
use[e->e]=true;
q[tail++]=e->e;
if (tail==maxn) tail=;
}
}
}
} int main()
{
freopen("di.in","r",stdin);
freopen("di.out","w",stdout); scanf("%d%d",&n,&m);
for (int a=;a<=m;a++)
scanf("%d%d%d",&edg[a][],&edg[a][],&edg[a][]);
for (int a=;a<=m;a++)
{
add_edge(a,edg[a][],edg[a][],edg[a][]);
add_edge(a,edg[a][],edg[a][],edg[a][]);
}
spfa();
int cnt=;
for (int a=n;a!=;a=f[a])
z[++cnt]=fe[a]->id;
int ans=-;
for (int a=;a<=cnt;a++)
{
en=;
memset(v,,sizeof(v));
for (int b=;b<=m;b++)
if (b!=z[a])
{
add_edge(b,edg[b][],edg[b][],edg[b][]);
add_edge(b,edg[b][],edg[b][],edg[b][]);
}
spfa();
if (dist[n]!=0x3f3f3f3f) ans=max(ans,dist[n]);
}
printf("%d\n",ans); return ;
}