#include <bits/stdc++.h>

using namespace std;

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

/// first = nod ; second = cost;
vector < pair < int, int > > L[50005];

/// first = cost ; second = nod;
priority_queue < pair < int, int > > Q;

int n, m, dp[50005], viz[50005];

void Citire()
{
    int x, y, c;
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        L[x].push_back({y, c});
    }
}

void Dijkstra()
{
    int nod, nou, cost, i;
    dp[1] = 0;
    for(i = 2; i <= n; i++)
        dp[i] = 1000000002;
    Q.push({0, 1}); /// Pentru a ajunge la nodul 1 costul este 0;
    while(!Q.empty())
    {
        nod = Q.top().second; /// Extrag nodul cu costul cel mai mic;
        Q.pop();
        if(viz[nod] == 0) /// Nu am vizitat nodul inca;
        {
            viz[nod] = 1; /// Il marchez ca fiind vizitat;
            for(auto w : L[nod]) /// Parcurg adiacentii nodului ales;
            {
                nou = w.first; /// Extrag nodul;
                cost = w.second; /// Extrag costul;
                if(dp[nou] > dp[nod] + cost) /// Verific daca am un drum cu un cost mai mic;
                {
                    dp[nou] = dp[nod] + cost;
                    Q.push({-dp[nou], nou}); /// Adaug in Q -dp[nou] pentru a fi sortat descrescator;

                }
            }
        }
    }

}

void Rezolvare()
{
    Dijkstra();
    for(int i = 2; i <= n; i++)
        if(dp[i] == 1000000002) fout << "0 ";
        else fout << dp[i] << " ";
    fout << "\n";
}

int main()
{
    Citire();
    Rezolvare();
    fin.close();
    fout.close();
    return 0;
}