#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];
bool InQ[NMax];
void Solve()
{
	int x;
	queue<int> qu;
	vector<int>::iterator it,itC;
	qu.push(0);
	InQ[0]=true;
	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;
				if (!InQ[*it])
					qu.push(*it),InQ[*it]=true;
			}
		InQ[x]=false;
	}
}

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;
}