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

#define N 50001
#define oo 0x3f3f3f3f //infinit

using namespace std;

int n, m;

struct nod
{
	int nd, cost;
	nod(){};
	nod(int x, int c){ nd = x; cost = c;}
};

vector<nod> a[N]; //lista de adiacenta
int d[N];

struct cmp// ca sa fie min-heap in fctie de distante
{
	bool operator()(const int &a, const int &b)const
	{
		if(d[a] > d[b]) return 1;
		return 0;
	}
};

void read()
{
	ifstream f("dijkstra.in");
	
	f>>n>>m;
	
	int x, y, c;
	while(m--)
	{
		f>>x>>y>>c;
		a[x].push_back(nod(y, c));
	}
}

void dijkstra()
{
	priority_queue<int, vector<int>, cmp> Q;
	
	memset(d, oo, sizeof(d));
	//ATENTIE memset merge DOAR PT 0x3f3f3f3f, -1, 0
	
	
	d[1] = 0;
	Q.push(1);
	
	
	while(!Q.empty())
	{
		int u = Q.top();
		Q.pop();
		
		for(vector<nod>::iterator i = a[u].begin(); i != a[u].end(); ++i)
			if(d[u] + i->cost < d[i->nd])
			{
				d[i->nd] = d[u] + i->cost;
				Q.push(i->nd);
			}
		
	}
	
	freopen("dijkstra.out","w",stdout);
	for(int i = 2; i <= n; ++i)
		printf("%d ", d[i] == oo ? 0 : d[i]);
	
}

int main()
{
	read();
	dijkstra();
	return 0;
}