#include <iostream>
#include <queue>
#include <algorithm>
#define MAXLEN 1005
#define inf 1<<29
using namespace std;
int map[MAXLEN][MAXLEN];
int vis[MAXLEN];
int dict[MAXLEN];
bool inq[MAXLEN];
void creat(int n)
{
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++)
{
if (i == j)
map[i][j] = ;
else
map[i][j] = map[j][i]= inf;
}
}
void build_map(int m)
{
for (int i = ; i < m; i++)
{
int b, e, v;
cin >> b >> e >> v;
map[b][e] = map[e][b] = v;
}
}
bool SPFA(int x, int n)
{
queue <int> Q;
memset(vis,,sizeof(vis));
memset(inq, false, sizeof(inq));
for (int i = ; i <= n; i++)
dict[i] = inf;
dict[x] = ;
inq[x]=true;
Q.push(x);
while (!Q.empty())
{
int q=Q.front();
Q.pop();
if(inq[q]==true)
inq[q]=false;
if (vis[q] > n)
return false;
vis[q]++;
for (int i = ; i <= n; i++)
{
if (map[q][i] < inf && dict[q] + map[q][i] < dict[i])
{
dict[i] = dict[q] + map[q][i];
if(inq[i]==false)
{
Q.push(i);
inq[i]=true;
}
}
}
}
return true;
}
int main()
{
int n,m;
while(cin >> n >> m&& n!= && m!=)
{
creat(n);
build_map(m);
int x=;
if (SPFA(x, n))
cout << dict[n] << endl; }
}