#include<bits/stdc++.h>

using namespace std;

const int maxn=1000+10;

const int INF=1000000000;

struct Edge{

	int v,d;

	Edge(int v,int d):v(v),d(d){}

	bool operator<(const Edge&a)

	const{return d>a.d;}

};

vector<Edge>Map[maxn];

int vis[maxn],dis[maxn];

void dijkstra(int n){

	priority_queue<Edge>Q;

	for(int i=1;i<=n;i++)dis[i]=INF;

	dis[1]=0;

	Q.push(Edge(1,dis[1]));

	while(!Q.empty()){

		Edge now=Q.top();Q.pop();

		if(vis[now.v])continue;

		vis[now.v]=1;

		printf("edge:%d\n",now.v);

		for(int i=0;i<Map[now.v].size();i++){

			Edge next=Map[now.v][i];

			if(dis[next.v]>dis[now.v]+next.d){

				dis[next.v]=dis[now.v]+next.d;

				Q.push(Edge(next.v,dis[next.v]));

				printf("%d %d\n",next.v,dis[next.v]);

			}

		}

	}

}

int main(){

	int n,m;

	while(scanf("%d%d",&n,&m)==2 &&n){

		for(int i=1;i<=n;i++)Map[i].clear();

		memset(vis,0,sizeof(vis));

		memset(dis,0,sizeof(dis));

		while(m--){

			int a,b,c;

			scanf("%d%d%d",&a,&b,&c);

			Map[a].push_back(Edge(b,c));

			Map[b].push_back(Edge(a,c));

		}

		dijkstra(n);

		for(int i=1;i<=n;i++)printf("%d ",dis[i]);

		printf("\n");

	}

	return 0;

}

/*

5 7

1 2 2

1 3 1

1 4 6

2 4 1

3 4 4

3 5 10

4 5 1

*/