#include <fstream>
#include <queue>
#include <vector>
#define NMAX 50002
#define INF 1e9

using namespace std;

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

struct ceva
{
    int nod, cost;
    ///structura care ajuta la punerea elementelor in vector direct in ordine crescatoare
    bool operator < (const ceva &x) const
    {
        return cost > x.cost;
    }
}p;

int n, m, C[NMAX];
bool viz[NMAX];
priority_queue<ceva> G;
vector<ceva> v[NMAX];

int main()
{
    int i, x, y, z;
    fin >> n >> m;              ///facem citirea
    for(i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        v[x].push_back({y, z}); ///adaugam in vector costul pentru a ajunge in nodul y
    }
    for(i = 2; i <= n; i++)
        C[i] = INF;             ///marcam toate costurile cu infinit
    C[1] = 0;                   ///costul de a ajunge in nodul 1 plecand din 1 este 0 (nu am muchie)
    G.push({1, 0});             ///il adaugam in coada pe 1 cu costul sau (adica 0)
    while(!G.empty())           ///cat timp mai avem elemente in coada
    {
        p = G.top();            ///scoatem primul nod din coada
        G.pop();                ///eliminam primul nod din coada
        if(viz[p.nod])          ///daca am vizitat deja acest nod
            continue;           ///trecem mai departe
        viz[p.nod] = 1;         ///marcam faptul ca am vizitat acest nod
        for(auto it:v[p.nod])
        {
            if(C[it.nod] > C[p.nod] + it.cost)  ///daca am gasit un cost mai mic prin care putem ajunge in nodul it.nod
            {
                C[it.nod] = C[p.nod] + it.cost; ///actualizam costul prin care putem ajunge acolo
                G.push({it.nod, C[it.nod]});     ///adaugam in coada noul cost gasit
            }
        }
    }
    for(i = 2; i <= n; i++)         ///parcurgem vectorul de costuri
    {
        if(C[i] != INF)             ///daca am vizitat nodul i
            fout << C[i] << ' ';    ///il afisam
        else                        ///altfel
            fout << 0 << ' ';       ///afisam 0
    }
    return 0;
}