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

#define pb push_back
#define MAXN 50100
#define INF 1000000000
int N, M, d[MAXN]; 
vector<int> edges[MAXN], costs[MAXN];

struct node
{
	int cost;
	int at;
};

bool operator< (const node &leftNode, const node &rightNode)
{
	if (leftNode.cost != rightNode.cost)
		return leftNode.cost > rightNode.cost;
	if (leftNode.at != rightNode.at)
		return leftNode.at > rightNode.at;
	return false;
}

priority_queue<node> pq;

//mn = make node
node mn (int cost, int at)
{
	node nod;
	nod.cost = cost;
	nod.at = at;
	return nod;
}

int main(void)
{
	ifstream in ("dijkstra.in");
	in >> N >> M;
    for(int i = 1; i <= M; i++)
	{
		int x, y, c; in >> x >> y >> c;
		edges[x].pb(y);
		costs[x].pb(c);
	}
	in.close();
    
    for (int i = 2; i <= N; i++) 
		d[i] = INF;
			
	int val, x;
	
	pq.push ( mn(0, 1) );
	
	while (!pq.empty())
	{
		val = (pq.top()).cost;
		x = (pq.top()).at;
		pq.pop();
		
		for (unsigned i = 0; i < edges[x].size(); i++)
		{
			if (d[ edges[x][i] ] > val + costs[x][i] )
			{
				d[ edges[x][i] ] = val + costs[x][i];
				pq.push( mn( d[ edges[x][i] ], edges[x][i] ) );
			}
		}
	}

	ofstream out ("dijkstra.out");
    for(int i = 2; i <= N; i++)
	{
		if (d[i] == INF)
			continue;
		out << d[i] << ' ';
	}
	out.close();

    return 0;
}