#include <bits/stdc++.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int NMAX = 50005, INF = 0x3F3F3F3F;
int n, m;
vector<int> dist;
vector<vector<pair<int, int>>> graph;
bitset<NMAX> used;
void dijkstra(int node)
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dist[node] = 0;
pq.push({0, node});
while (!pq.empty())
{
node = pq.top().second;
pq.pop();
if (!used[node])
{
for (auto &[neighbour, cost] : graph[node])
if (dist[node] + cost < dist[neighbour])
{
dist[neighbour] = dist[node] + cost;
pq.push({dist[neighbour], neighbour});
}
used[node] = 1;
}
}
}
int main()
{
f >> n >> m;
dist.resize(n + 1, INF);
graph.resize(n + 1);
for (int i = 1; i <= m; i++)
{
int x, y, c;
f >> x >> y >> c;
graph[x].push_back({y, c});
}
dijkstra(1);
for (int i = 2; i <= n; i++)
if (dist[i] == INF)
g << 0 << ' ';
else
g << dist[i] << ' ';
return 0;
}