#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define N 50001
#define INF 100000
int n, m, h[N], p[N], end, d[N];
vector < pair <int, int> > v[N];
void swap(int a, int b, int V[])
{
int aux;
aux = V[a];
V[a] = V[b];
V[b] = aux;
}
void down_heap(int i, int n)
{
int j = i;
if (2 * i <= n && h[j] > h[2 * i])
j = 2 * i;
if (2 * i + 1 <= n && h[j] > h[2 * i + 1])
j = 2 * i + 1;
if (i != j)
{
swap(i, j, p);
down_heap(j, n);
}
}
void up_heap(int i, int n)
{
if (i > 1 && h[i] < h[i / 2])
{
swap(i, i / 2, p);
swap(i, i / 2, h);
up_heap(i / 2, n);
}
}
void solve()
{
int i, k;
h[end = 1] = 1;
for (i = 2; i <= n; ++ i)
d[i] = INF;
while (end)
{
k = h[1];
for (i = 0; i < v[k].size(); ++ i)
if (d[v[k][i].first] >= d[k] + v[k][i].second)
{
d[v[k][i].first] = d[k] + v[k][i].second;
if (p[v[k][i].first])
{
up_heap(p[v[k][i].first], end);
down_heap(p[v[k][i].first], end);
}
else if (p[v[k][i].first] != INF)
{
h[++ end] = v[k][i].first;
up_heap(end, end);
}
}
swap(1, end, h);
-- end;
down_heap(1, end);
p[k] = INF;
}
}
int main()
{
int i, a, b, c;
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%d%d", &n, &m);
for (i = 1; i <= m; ++ i)
{
scanf("%d%d%d", &a, &b, &c);
v[a].push_back(make_pair(b, c));
v[b].push_back(make_pair(a, c));
}
solve();
for (i = 2; i <= n; ++ i)
printf("%d ", d[i]);
printf("\n");
}