#include <bits/stdc++.h>

#define NMAX 100005
#define INF 0x3f3f3f3f

using namespace std;

typedef pair<int, int> Pair;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int n;
vector<vector<Pair>> a(NMAX);
// a[i][indice].first = j -> exista muchie intre i si j, a[i][indice].second -> costul muchiei intre i si j

void citire()
{
    int x, y, m, c;
    in >> n >> m;
    while (m--)
    {
        in >> x >> y >> c;
        a[x].emplace_back(y, c);
    }
}

void dijkstra(int start)
{
    priority_queue<Pair, vector<Pair>, greater<Pair>> pq; // coada de tip vector mereu ordonat crescator
    // fiind pair.first = distanta, pair.second = varf, se va ordona dupa distanta crescatoare
    vector<int> dist(NMAX, INF); // dist[i] -> distanta minima de la nodul start la nodul i

    pq.push(make_pair(0, start));
    dist[start] = 0;

    while (!pq.empty()) // cat timp nu sunt construite toate distantele(coada nu e goala)
    {
        int u = pq.top().second; // primul varf din coada
        pq.pop();

        for (auto i = a[u].begin(); i != a[u].end(); i++) // parcurg varfurile cu care formeaza muchie
        {
            int v = (*i).first;       // varful
            int weight = (*i).second; // costul

            if (v == 5)
                cout << dist[v] << ' ';
            if (dist[u] + weight < dist[v])
            {
                // daca distanta de la nodul curent u la un nod vecin v prin costul acestei muchii
                // e mai mica decat distanta deja stiuta pentru v, atunci schimbam distanta minima
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v)); // pun nodul cu distanta sa minima in coada

                // aici intervina coada prin ordonare crescatoare...
                // daca exista mai multe distante pana la un nod v se vor adauga toate in coada
                // dar fiindca se ordoneaza crescator se va lua cel cu cea mai mica distanta ca primul element pq.top()
            }
        }
    }

    for (int i = 2; i <= n; i++)
    {
        if (dist[i] == INF)
            dist[i] = 0;
        out << dist[i] << ' ';
    }
}

int main()
{
    citire();
    dijkstra(p);
    return 0;
}