#include<stdio.h>
#include<vector>
#include<queue>
#define NMAX 50001
#define INF 9999999
using namespace std;

FILE *fin = fopen("dijkstra.in","r");
FILE *fout = fopen("dijkstra.out","w");

vector < pair < int,int > > v[NMAX];
queue < int > coada;
int n,m,i,j,d[NMAX];

void read()
{
	int x,y,c;
	fscanf(fin,"%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		fscanf(fin,"%d%d%d",&x,&y,&c);
		v[x].push_back( make_pair (y,c));
		//v[y].push_back( make_pair (x,c));
	}
}

void init()
{
	for(i=1; i<=n ;i++)
		d[i] = INF;
	d[1] = 0;
}

void solve()
{
	int nod;
	coada.push(1);
	while(!coada.empty())
	{
		nod = coada.front();
		coada.pop();
		for(j=0;j<v[nod].size();j++)
			if(d[v[nod][j].first] > d[nod] + v[nod][j].second)
			{
				d[v[nod][j].first] = d[nod] + v[nod][j].second;
				coada.push(v[nod][j].first);
			}				
	}
	
	for(i=2;i<=n;i++)
	{
		if(d[i] != INF)
			fprintf(fout,"%d ",d[i]);
		else
			fprintf(fout,"%d ",0);
	}
}

int main()
{
	read();
	init();
	solve();
}