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

#define MAXSIZE 50001
#define oo 0x3F3F3F3F

#define cost first
#define location second

int nodes;
vector<int> dist(MAXSIZE,oo);
vector< pair<int,int> > graph[MAXSIZE];
priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > myQueue;

void read();
void dijkstra(int startNode);
void write();

int main()
{
	read();
	dijkstra(1);
	write();

    return (0);
}

void read()
{
	ifstream in("dijkstra.in");
	int edges,from,to,cost;

	in >> nodes >> edges;

	for(int i=1;i<=edges;i++)
	{
		in >> from >> to >> cost;

		graph[from].push_back(make_pair(cost,to));
	}

	in.close();
}

void dijkstra(int startNode)
{
	dist[startNode] = 0;

	pair<int,int> currentNode;
	vector< pair<int,int> >::iterator neighbour;
	vector< pair<int,int> >::iterator end;

	myQueue.push(make_pair(0,startNode));

	while(!myQueue.empty())
	{
		currentNode = myQueue.top();
		myQueue.pop();

		end = graph[currentNode.location].end();

		for(neighbour=graph[currentNode.location].begin();neighbour!=end;neighbour++)
			if(dist[neighbour->location] > dist[currentNode.location] + neighbour->cost)
			{
				dist[neighbour->location] = dist[currentNode.location] + neighbour->cost;
				myQueue.push(make_pair(dist[neighbour->location],neighbour->location));
			}
	}
}

void write()
{
	ofstream out("dijkstra.out");

	for(int i=2;i<=nodes;i++)
		if(dist[i] == oo)
			out << "0 ";
		else
			out << dist[i] << " ";

	out << "\n";

	out.close();
}