#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int MaxN = 50005;
const int Inf = 0x3f3f3f3f;

using P = pair <int, int>;
using VP = vector <P>;
using VVP = vector <VP>;
VVP G;  //graful propriu-zis
int n, m;
bool vizitat[MaxN]; // aici retinem daca un anume nod se afla sau nu in coada de prioritati
int distanta[MaxN]; // aici retinem distanta de la nodul de start, la nodul i (d[i] = distanta de la nodul 1 la nodul i)

void Citire();
void Dijkstra(int nod_start);

int main()
{
    Citire();
    for (int i = 1; i <= n; ++i)
        distanta[i] = Inf;
    distanta[1] = 0;

    Dijkstra(1);

    for (int i = 2; i <= n; ++i)
        fout << distanta[i] << ' ';
}
void Dijkstra(int nod_start)
{
    priority_queue<P, VP, greater<P> > Q;   //min-HEAP (coada de prioritati pairuri. Elementele sunt ordonate in functie de cele mai mici costuri) (in functie de .first)
    Q.push({distanta[nod_start], nod_start});     // adaugam nodul de start in coada, el avand costul 0;
    vizitat[nod_start] = true;

    while (!Q.empty())
    {
        int cost_curent = Q.top().first;       //extragem costul nodului din capul cozii
        int nod_curent = Q.top().second;       //si pe acesta

        Q.pop();
        vizitat[nod_curent] = false;

        for (int i = 0; i < G[nod_curent].size(); ++i)
        {
            P urmator = {G[nod_curent][i].second, G[nod_curent][i].first}; //extragem vecinii nodului curent; intai COSTUL si apoi NODUL pentru
                                                                            // a le introduce in coada in ordinea corecta.
            if(distanta[nod_curent] + urmator.first < distanta[urmator.second])
            {
                distanta[urmator.second] = distanta[nod_curent] + urmator.first;       //actualizam distanta pana la nodul vecin

                if (!vizitat[urmator.second])
                {
                    Q.push(urmator);                //adaugam in coada costul si vecinul nodului curent
                    vizitat[urmator.second] = true;
                }
            }

        }
    }
}

void Citire()
{
    fin >> n >> m;
    int x, y, z;

    G = VVP(n + 1);

    for (int i = 1; i <= m; ++i)
    {
        fin >> x >> y >> z;
        G[x].push_back(make_pair(y, z));  // retinem graful intr-un singur sens, acesta fiind orientat
    }
}