#include <bits/stdc++.h>

#define NMAX 50005
#define INF 0x3f3f3f3f

using namespace std;

typedef pair<int, int> Pair;

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

int n, m, p, x, y, c;
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()
{
    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(1);
    return 0;
}