//Slow but 100%working
#include <fstream>
#include <iostream>
#include <vector>

#define INF 0x3f3f3f3f
#define NMAX 50001

using namespace std;

int d[NMAX];
vector<int> G[NMAX],C[NMAX];
int N;
int viz[NMAX];

int min()
{
	int min=INF;
	int imin=-1;
	for(int i=1;i<=N;i++)
		if (d[i]<=min && !viz[i]) 
		{
			min=d[i];
			imin=i;
		}
	return imin;
}

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 init()
{
	for(int i=2;i<=N;i++)
		d[i]=INF;
}

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 dij()
{
	int x;
	unsigned int i;
	x=1;
	while(d[x]!=INF && x!=-1)
	{
		x=min();
		viz[x]++;
		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];
		}
	}
}

void Debug()
{
	cout<<"Lista de vecini:\n";
	for(int j=1;j<=N;j++)
		{
			cout<<j<<": ";
			for(unsigned int i=0;i<G[j].size();i++)
				cout<<G[j][i]<<" ";
			cout<<"\n";
		}
	cout<<"Lista de costuri:\n";
	for(int j=1;j<=N;j++)
		{
			cout<<j<<": ";
			for(unsigned int i=0;i<C[j].size();i++)
				cout<<C[j][i]<<" ";
			cout<<"\n";
		}
}

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