#include<fstream>
#include<queue>
#include<vector>

using namespace std;

const int MaxN = 50001;
const int Inf = 0x3f3f3f3f;

int n,m,d[MaxN];
bool inQ[MaxN];
vector< pair<int,int> > G[MaxN];
queue<int> Q;

inline void read()
{
	ifstream f("dijkstra.in");
	f >> n >> m;
	int x,y,c;
	for( int i = 1 ; i <= m ; i++ )
		{
			f >> x >> y >> c;
			G[x].push_back(make_pair(y,c));
		}
	f.close();
}

void bellman_ford()
{
	int nod;
	vector< pair<int,int> >::iterator it;
	for( int i = 1 ; i <= n ; i++ )
		{
			d[i] = Inf;
			inQ[i] = false;
		}
	d[1] = 0;
	Q.push(1);
	inQ[1] = true;
	while( !Q.empty() )
		{
			nod = Q.front();
			Q.pop();
			inQ[nod] = false;
			for( it = G[nod].begin() ; it != G[nod].end() ; ++it )
				if( d[it-> first] > d[nod] + it-> second )
					{
						d[it->first] = d[nod] + it->second;
						if( !inQ[it->first] )
							{
								Q.push(it->first);
								inQ[it->first] = true;
							}
					}
		}
}

inline void print()
{
	ofstream g("dijkstra.out");
	for( int i = 2 ; i <= n ; i++ )
		g << ((d[i]<Inf)?d[i]:0) << ' ';
	g.close();
}

int main()
{
	read();
	bellman_ford();
	print();
	return 0;
}