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

#define INF 0x3f3f3f3f

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,m;
vector<pair<int,int>> G[50005];
int D[50005];

void read();
void solve();
void print();

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

void read()
{
	int a,b,c;
	fin>>n>>m;
	for(int i=0;i<m;i++)
	{
		fin>>a>>b>>c;
		G[a].push_back(make_pair(b,c));
	}
}

void solve()
{
	queue<int> Q;
	bool InQueue[50005];
	memset(D,INF,sizeof(D));
	memset(InQueue,false,sizeof(InQueue));
	D[1] = 0;
	InQueue[1] = true;
	Q.push(1);
	while(!Q.empty())
	{
		int nod = Q.front();
		Q.pop();
		InQueue[nod] = false;
		for (vector<pair<int,int>>::iterator it = G[nod].begin(); it != G[nod].end(); ++it)
		{			
			if(D[nod] + it->second < D[it->first])
			{
				D[it->first] = D[nod] + it->second;
			}
			if(!InQueue[it->first])
			{
				Q.push(it->first);
				InQueue[it->first] = true;
			}
		}
	}
}

void print()
{
	for(int i=2;i<=n;i++)
	{
		fout<<(D[i] != INF ? D[i] : 0)<<' ';
	}
}