#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;

struct edge
{
	int y,w,next;
}  map[100010];

struct node
{
	int y,d;
	node(){}
	node(int _y,int _d):y(_y),d(_d){}
	bool operator < (const node a)
	const
	{
		return a.d < d;
	} 
};

bool v[260];
int head[260],tot,dis[260],n,m,x,y,w,ans,len,temp;

inline void add(int x,int y,int w)
{
	tot++;
	map[tot].y = y;
	map[tot].w = w;
	map[tot].next = head[x];
	head[x] = tot;
	return;
}

inline int dij()
{
	memset(v,0,sizeof(v));
	memset(dis,0x7f,sizeof(dis));
	dis[1] = 0;
	node now,next;
	priority_queue<node> q;
	q.push(node(1,0));
	while (!q.empty())
	{
		now = q.top();
		q.pop();
		v[now.y] = 1;
		for (int i = head[now.y];i != -1;i = map[i].next)
		{
			if (v[map[i].y]) continue;
			next = node(map[i].y,now.d+map[i].w);
			if (dis[next.y] > next.d)
			{
				dis[next.y] = next.d;
				q.push(next);
			}
		}
	}
	if (dis[n] < 2100000000)
	return dis[n];
	else
	return 0;
}

int main()
{
	freopen("rblock.in","r",stdin);
	freopen("rblock.out","w",stdout);
	scanf("%d%d",&n,&m);
	tot = 0;
	memset(head,-1,sizeof(head));
	for (int i = 1;i <= m;i++)
	{
		scanf("%d%d%d",&x,&y,&w);
		add(x,y,w);
		add(y,x,w);	
	}
	len = dij();
	ans = 0;
	for (int i = 1;i <= m;i++)
	{
		map[i*2-1].w <<= 1;
		map[i*2].w <<= 1;
		temp = dij() - len;
		if (temp > 0 && ans < temp)
		ans = temp;
		map[i*2-1].w >>= 1;
		map[i*2].w >>= 1;
	}
	printf("%d\n",ans);
	return 0;
}