#include<stdio.h>
#include<vector>
#define NMAX 50002
#define Inf 2000000000
using namespace std;
//ifstream fin("dijkstra.in");
//ofstream fout("dijkstra.out");
int n,m,i,x,y,d[NMAX],c[1<<20],j;
vector<int>A[NMAX];
vector<int>cost[NMAX];
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	//fin>>n>>m;
	for (i=1;i<=n;i++)
		d[i]=Inf;
	d[1]=0;
	for (i=1;i<=m;i++)
	{
		//fin>>x>>y>>j;
		scanf("%d%d%d",&x,&y,&j);
		cost[x].push_back(j);
		A[x].push_back(y);
	}
	int ic,sc,z;
	ic=sc=1; c[ic]=1;
		while (ic<=sc)
			{
				z=c[ic];
				for (y=0;y<A[z].size();y++)
					if (d[z]+cost[z][y]<d[A[z][y]])
					{
						d[A[z][y]]=d[z]+cost[z][y];
						c[++sc]=A[z][y];
					}
				ic++;
			}
		for (i=2;i<=n;i++)
			//if (d[i]!=Inf)fout<<d[i]<<' ';
			if (d[i]!=Inf) printf("%d ",d[i]);
			else
				//fout<<0<<' ';
				printf("0 ");
//fout.close();
return 0;}