#include<iostream>
#include<string>
#include<string.h>
#include<vector>
#include<stdio.h>
#include <queue>
#include<algorithm>
using namespace std;
const int maxn=205;

vector<pair<int,int>>E[maxn];
int n,m;
int d[maxn],inq[maxn];//标记在不在队列

void spfa(int s,int t)
{
	queue<int>q;
	q.push(s),d[s]=0,inq[s]=1;
	while(!q.empty())
	{
		int now=q.front ();
		q.pop();inq[now]=0;
		//遍历顶点所有边
		for(int i=0;i<E[now].size();i++)
		{
			int v=E[now][i].first;
			if(d[v]>d[now]+E[now][i].second )
			{
				d[v]=d[now]+E[now][i].second ;
				if(inq[v]==1)continue;
				inq[v]=1;
				q.push(v);
			}
		}
	}
	cout<<d[t]<<endl;
}

void init()
{
	for(int i=0;i<maxn;i++) E[i].clear();
	for(int i=0;i<maxn;i++) inq[i]=0;
	for (int i=0;i<maxn;i++)d[i]=1e9;
}
int main()
{
	while(cin>>n>>m)
	{
		if(n+m==0)break;
		init();
		for(int i=0;i<m;i++)
		{
			int x...