#include<fstream>
#include<queue>
#include<vector>
#include<bitset>
using namespace std;

#define INF 0x3f3f3f3f
#define NMAX 50002

void read();
void dijkstra();
void write();

vector< pair<int, int> > a[NMAX];
queue<int > Q;
bitset<50002> s;

int n, m;
int d[NMAX];

int main()
{
	read();
	dijkstra();
	write();
	return 0;
}

void read()
{
	ifstream fin("bellmanford.in");
	
	fin >> n >> m;
	int x, y, z;
	
	for(int i = 1; i <= m; ++i)
	{
		fin >> x >> y >> z;
		a[x].push_back( make_pair(y, z) );
	}
	
	fin.close();
}

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


void dijkstra()
{
	s[1] = 1;
	vector< pair<int, int> >::iterator it;
	Q.push(1);
	
	for(int i = 2; i <= n; i++) 
		d[i] = INF;
	
	while( !Q.empty() )
	{
		int k = Q.front();
		for( it = a[k].begin(); it != a[k].end(); ++it)
			if( d[ it -> first] > d[k] + it -> second)
			{
				 d[ it -> first] = d[k] + it -> second;
				 if( s[it -> first] == 0 )
				 {
					Q.push( it -> first );
					s[ it -> first] = 1;
				 }
			}
			
		s[k] = 0;
		Q.pop();
	}
}