//100% working
#include<fstream>
#include <vector>
#include <queue>

#define NMAX 50001
#define INF 0x3f3f3f3f
using namespace std;

vector<int> G[NMAX],C[NMAX];
int d[NMAX];
int Q[1<<25],st,dr;
int N;
int is[NMAX];

void init()
{
	memset(d,INF,sizeof(d));
	d[1]=0;
	Q[++dr]=1;
	is[1]=1;
}

void citire()
{
	int M;
	ifstream fin("dijkstra.in");
	fin>>N>>M;
	int x,y,c;
	for(int i=1;i<=M;i++)
		{
			fin>>x>>y>>c;
			G[x].push_back(y);
			C[x].push_back(c);
		}
	fin.close();
}

void afisare()
{
	ofstream fout("dijkstra.out");
	for(int i=2;i<=N;i++)
		if(d[i]==INF) fout<<"0 ";
	else 
		fout<<d[i]<<" ";
	fout<<"\n";
	fout.close();
}

void bell()
{
	int x;
	unsigned int i;
	while(st<=dr)
	{
		x=Q[st++];
		is[x]=0;
		for(i=0;i<G[x].size();i++)
		{
			if(d[x]+C[x][i]<d[G[x][i]])
			{
				d[G[x][i]]=d[x]+C[x][i];
				if(!is[G[x][i]])
				{
					Q[++dr]=G[x][i];
					is[G[x][i]]=1;
				}
			}
		}
	}
}

int main(int argc,char *argv[])
{
	init();
	
	citire();
	
	bell();
	
	afisare();
}