#include <stdio.h>
#include <vector>
#include <queue>
#define NMax 50000
#define MMax 250000
using namespace std;

const char IN[]="dijkstra.in",OUT[]="dijkstra.out";

int N,M;

vector<int> a[NMax];
vector<int> C[NMax];

int dist[NMax];

void Solve()
{
	int x;
	queue<int> qu;
	vector<int>::iterator it,itC;
	qu.push(0);
	dist[0]=0;
	
	while (!qu.empty())
	{
		x=qu.front();
		qu.pop();
		
		for (it=a[x].begin(),itC=C[x].begin();it<a[x].end();++it,++itC)
			if (dist[*it]==-1 || dist[*it]> dist[x] + *itC)
			{
				dist[*it]= dist[x] + *itC;
				qu.push(*it);
			}
	}
}

int main()
{
	int i,x,y,c;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&M);
	for (i=0;i<M;i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		a[x-1].push_back(y-1);
		C[x-1].push_back(c);
	}
	fclose(stdin);
	for (i=1;i<N;i++) dist[i]=-1;
	
	Solve();
	
	freopen(OUT,"w",stdout);
	for (i=1;i<N;i++)
		printf("%d ", (dist[i]==-1) ? 0 : dist[i]);
	fclose(stdout);
	
	return 0;
}