#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 2e9;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
struct Node {
int node, cost;
bool operator<(const Node& other) const {
return cost > other.cost;
}
};
int n, m;
int dist[50100];
//bool visited[50100];
priority_queue<Node> Q;
vector<vector<pair<int, int>>> adjList;
void dijkstra(int start)
{
dist[start] = 0;
for(int i = 1; i <= n; i++)
dist[i] = INF;
Q.push({start, 0});
while(!Q.empty())
{
int vertex = Q.top().node;
int c = Q.top().cost;
Q.pop();
//if(visited[vertex] == 0)
//{
// visited[vertex] = 1;
//cout << vertex << ' ' << c << '\n';
int len = adjList[vertex].size();
for(int i = 0; i < len; i++)
{
int v = adjList[vertex][i].first;
int d = adjList[vertex][i].second;
//cout << dist[v] << ' ' << d << '\n';
if(c + d < dist[v])
{
dist[v] = c + d;
Q.push({v, dist[v]});
}
}
//}
}
}
int main()
{
in >> n >> m;
adjList.resize(n + 5);
for(int i = 1; i <= m; i++)
{
int x, y, cost;
in >> x >> y >> cost;
adjList[x].push_back({y, cost});
}
dijkstra(1);
for(int i = 2; i <= n; i++)
{
if(dist[i] == INF)
out << 0 << ' ';
else
out << dist[i] << ' ';
}
out << '\n';
return 0;
}