#include <bits/stdc++.h>
#define INF (1 << 30)
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n, m, a[50005], b[50005], z, heap[50005], dist[50005];
vector <pair <int, int> > muchii[50005];
void schimba(int k1, int k2)
{
    swap(heap[k1], heap[k2]);
    swap(a[b[k1]], a[b[k2]]);
    swap(b[k1], b[k2]);
}
void UpHeap(int k)
{
    if (k / 2 < 1) return;
    if (heap[k] < heap[k / 2])
    {
        schimba(k, k / 2);
        UpHeap(k / 2);
    }
}
void DownHeap(int k)
{
    if (k * 2 > z) return;
    if (heap[k] > heap[k * 2] || heap[k] > heap[k * 2 + 1])
    {
        if (heap[k * 2] < heap[k * 2 + 1])
        {
            schimba(k, k * 2);
            DownHeap(k * 2);
        }
        else
        {
            schimba(k, k * 2 + 1);
            DownHeap(k * 2 + 1);
        }
    }
}
void Add(int nod, int val)
{
    heap[++z] = val;
    b[z] = nod;
    a[nod] = z;
    UpHeap(z);
}
void Del(int k)
{
    schimba(1, z);
    heap[z] = INF;
    --z;
    DownHeap(1);
}
int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        muchii[x].push_back({y, cost});
    }
    Add(1, 0);
    for (int i = 2; i <= n; ++i)
    {
        dist[i] = INF;
        Add(i, INF);
    }
    while (z)
    {
        int nod = b[1];
        int val = heap[1];
        Del(1);
        for (int j = 0; j < muchii[nod].size(); ++j)
        {
            int nod2 = muchii[nod][j].first;
            int cost = muchii[nod][j].second;
            if (dist[nod2] > dist[nod] + cost)
            {
                dist[nod2] = dist[nod] + cost;
                heap[a[nod2]] = dist[nod2];
                UpHeap(a[nod2]);
            }
        }
    }
    for (int i = 2; i <= n; ++i)
    {
        if (dist[i] == INF) dist[i] = 0;
        fout << dist[i] << " ";
    }
    fin.close();
    fout.close();
}