#include<bits/stdc++.h>
using namespace std;

#define max1 10000000

const int maxn=1000;
int gmap[maxn][maxn];
int visited[maxn];
int dist[maxn];



int dj(int n){//n表示n结点
	dist[1] = 0;
	//先初始化dist数组
	for(int i = 2;i<=n;i++){
		if(gmap[1][i]>0){
			dist[i] = gmap[1][i];
		}else{
			dist[i] = max1;//表示不可达 
		}
	} 
	
	

	int k;//记录最小元素下标 
	for(int i = 1;i<n;i++){//n-1次 结点进去 
	
		int min = max1;
		
		for(int j = 2;j<=n;j++){
			if(dist[j]<min&&!visited[j]){
				min = dist[j];
				k = j;
			}
		}

		visited[k] = 1;
		
		//更新距离
		
		for(int l = 2;l<=n;l++){
			if(!visited[l]&&gmap[k][l]!=0&&dist[l] > dist[k] + gmap[k][l]){
				dist[l] = dist[k] + gmap[k][l];
			}
		} 
		
		
	}


	
}
int main(){
	int n,m;
	while(cin>>n>>m){
		memset(visited,0,sizeof(visited));
		memset(gmap,0,sizeof(gmap));
		memset(dist,0,sizeof(dist));
		//n为结点数 m为边 
		if(n==0&&m==0)break...