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

using namespace std;

#define MAX_N 50005
#define INF 0x3f3f3f

#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)
#define x first
#define c second

vector < pair<int, int> > G[MAX_N];
int D[MAX_N];
int N, M;


struct cmp
{
	bool operator()(const int &a, const int &b)
	{
		return D[a] > D[b];
	}
};

priority_queue <int, vector <int>, cmp> Q;

void citire()
{
	scanf("%d %d",&N, &M);
	
	while(M--)
	{
		int x, y, c;
		scanf("%d %d %d",&x, &y, &c);
		G[x].push_back( make_pair(y,c) );
	}
}

void solve()
{
	memset(D, INF, sizeof D);
	
	Q.push(1);
	D[1] = 0;
	
	for(;!Q.empty(); Q.pop())
	{
		int nod = Q.top();
		
		foreach(G[nod])
			if(D[it -> x] > D[nod] + it -> c)
			{
				D[it -> x] = D[nod] + it -> c;
				Q.push(it -> x);
			}
	}
	
	for(int i = 2; i <= N; ++i)
		printf("%d ",D[i]);
}

int main()
{
	freopen("dijkstra.in","rt",stdin);
	freopen("dijkstra.out","wt",stdout);
	
	citire();
	solve();
}