#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
typedef pair<int, int> iPair;
const int NMAX = 1e4 * 5 + 1;
int n, m;
vector<iPair> adj[NMAX];
priority_queue<iPair, vector<iPair>, greater<iPair>> Q;
vector<int> d(NMAX, INF);
void addEdge(int x, int y, int w)
{
adj[x].push_back(make_pair(y, w));
}
void read()
{
int x, y, w;
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
fin >> x >> y >> w;
addEdge(x, y, w);
}
}
void Djikastra(int k)
{
Q.push(make_pair(0, k));
d[k] = 0;
while (!Q.empty())
{
int x = Q.top().second;
Q.pop();
for (auto i : adj[x])
{
int v = i.first, w = i.second;
if (d[v] > d[x] + w)
{
d[v] = d[x] + w;
Q.push(make_pair(d[v], v));
}
}
}
for (int i = 2; i <= n; i++)
fout << d[i] << ' ';
}
int main()
{
read();
Djikastra(1);
return 0;
}
/*
5 6
1 2 1
1 4 2
4 3 4
2 3 2
4 5 3
3 5 6
*/