#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int NMAX = 50005;
const int INF = 2e9;

struct Edge
{
	int y, cost;
	Edge(int y, int cost)
	{
		this->y = y;
		this->cost = cost;
	}
};

struct Node
{
	int nod, cost;
	Node(int nod, int cost)
	{
		this->nod = nod;
		this->cost = cost;
	}
	bool operator<(const Node& other) const
	{
		return cost > other.cost;
	}
};

vector<Edge>G[NMAX];
int distMin[NMAX];
int n, m;


void read()
{
	fin >> n >> m;
	while (m--)
	{
		int x, y, cost;
		fin >> x >> y >> cost;
		G[x].push_back(Edge(y, cost));
	}
	for (int i = 2; i <= n; i++)
		distMin[i] = INF;
}

void dijkstra(int start_node)
{
	priority_queue<Node>pq;
	pq.push(Node(start_node, 0));
	distMin[start_node] = 0;

	while (!pq.empty())
	{
		Node u = pq.top();
		pq.pop();

		distMin[u.nod] = min(distMin[u.nod], u.cost);
		for (Edge e : G[u.nod])
			if (u.cost + e.cost < distMin[e.y])
			{
				distMin[e.y] = u.cost + e.cost;
				pq.push(Node(e.y, u.cost + e.cost));
			}
	}
}

void solve()
{
	dijkstra(1);
	for (int i = 2; i <= n; i++)
		fout << distMin[i] << ' ';
	fout << '\n';
}

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