#include<fstream>
#include<vector>
#include<set>
using namespace std;

#define INF 0x3f3f3f3f

void read();
void solve();
void write();

set<pair<int, int> > sol;
int n, m;
vector<vector<int> > a, c;
vector<int > d;

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

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

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

void solve()
{
	for(int i = 1; i <= n; i++) d[i] = INF;
	
	sol.insert(make_pair(0, 1) );
	
	int cost, nod;
	while( sol.size() > 0 )
	{
		cost = ( *sol.begin() ).first;
		nod =  ( *sol.begin() ).second;
		sol.erase( *sol.begin() );
		for( int i = 0; i < (int)a[nod].size(); ++i)
			if( d[ a[nod][i] ] > cost + c[nod][i])
			{
				d[ a[nod][i] ] = cost + c[nod][i];
				s[ a[nod][i] ] = 1;
				sol.insert( make_pair( d[ a[nod][i] ], a[nod][i] ) );
				s[ a[nod][i] ] = 1;
			    
			}
	}

}