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

using namespace std;

#define f first
#define s second
#define mp make_pair
#define pb push_back

const int N=50001;
const int oo=1<<30;

vector<pair<int,int> > G[N];
vector<int> dst;
int n,m;

void read ()
{

	ifstream in ("dijkstra.in");
	
	in>>n>>m;
	
	for(int x,y,c;m;--m)
	{
		in>>x>>y>>c;
		G[x].pb(mp(y,c));
	}

}

void solve ()
{
	
	priority_queue<pair<int,int> > Q;
	dst.resize(n+1,oo);
	dst[1]=0;
	
	for(Q.push(mp(0,1));Q.size();)
	{
		int nd=Q.top().s;
		Q.pop();
		for(vector<pair<int,int> >::iterator it=G[nd].begin();it<G[nd].end();++it)
			if(dst[it->f]>dst[nd]+it->s)
			{
				dst[it->f]=dst[nd]+it->s;
				Q.push(mp(-dst[it->f],it->f));
			}
	}
	
}

void out ()
{
	freopen ("dijkstra.out","w",stdout);
	
	for(int i=2;i<=n;++i)
		if(dst[i]==oo)
			printf("0 ");
		else
			printf("%d ",dst[i]);

}

int main ()
{
	
	read ();
	solve ();	
	out ();
	
	return 0;

}