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

#define pb push_back

const int INF = 500000000;
const int NMAX = 50005;
const char Input[] = "dijkstra.in";
const char Output[] = "dijkstra.out";

class state
{
public:
	int nod,cost;
	
	state(int nod,int cost)
	{
		this->nod = nod;
		this->cost = cost;
	}
};

class comparer
{
public:
	bool operator()(state s1,state s2)
	{
		return s1.cost < s2.cost;
	}
};

vector<int> g[NMAX],c[NMAX];
priority_queue<state,vector<state>,comparer> H;
int N,M,dmin[NMAX];
ifstream fin(Input);
ofstream fout(Output);

void read()
{
	int i,e1,e2,cost;
	
	fin>>N>>M;
	
	for(i=1; i<=M; i++)
	{
		fin>>e1>>e2>>cost;
		g[e1].pb(e2);
		c[e1].pb(cost);
	}
}

void dijkstra()
{
	state s = state(1,0);
	int nod , cost,i;
	
	H.push(s);
	
	for(i=1; i<=N; i++)
		dmin[i] = INF;
	
	while(!H.empty()){
		s = H.top();
		H.pop();
		nod = s.nod;
		cost = s.cost;
		
		for(i=0; i<g[nod].size(); i++)
			if(dmin[g[nod][i]] > cost + c[nod][i])
			{
				dmin[g[nod][i]] = cost + c[nod][i];
				s = state(g[nod][i],dmin[g[nod][i]]);
				H.push(s);
			}
	}
}

int main()
{
	read();
	dijkstra();
	
	int i;
	
	for(i=2; i<=N; i++)
		if(dmin[i] == INF)
			fout<<0<<" ";
		else
			fout<<dmin[i]<<" ";
	
	fin.close();
	fout.close();
	return 0;
}