//----------DISJKSTRA

// O(mlogn)

// d[i]= inf
// d[s]=0 --sursa
// priority que push({-d[s], s})
// cat timp mai avem noduri in coada de prioritati !pq.empty
//     nod =pq.top.second
//      pq.pop();
//     if vizitat[nod]
//         continue;
//     else vizitam

//     for x apartine L[nod] --lista de adiacenta cu perechi de nod-cost 
//         vecin=x.first
//         cost =x.second
//         if d[vecin]>d[nod]+cost 
//             d[vecin] =d[nod] +cost 
//             pq.push ({-d[vecin], vecin})


// #include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <queue>

using namespace std;

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

int n,m,x,y,c,nod, vecin, cost;
int i;
vector<vector<pair<int, int>>>L;
vector<int> d;
vector<bool> vizitat;
priority_queue<pair<int, int>> pq;


void citire(){
    cin>>n>>m;

    vizitat.resize(n+1, false);
    L.resize(n + 1);
    d.resize(n + 1);
    for(i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        L[x].push_back({y,c});
    }
}


void initializare(){
    for(i=1;i<=n;i++)
    {
        d[i]=INT_MAX;
    }

    d[1]=0;
    pq.push({-d[1], 1});

}


void Disjkstra(){
    citire();
    initializare();
    while(!pq.empty()){

        nod = pq.top().second;
        pq.pop();
        if(vizitat[nod])
        {    
            continue;
        }
        vizitat[nod]=1;

        for(auto x : L[nod])
        {
            vecin = x.first;
            cost = x.second;

            if(d[vecin] > d[nod]+cost)
            {
                d[vecin] = d[nod]+cost;
                pq.push({-d[vecin], vecin});
            }

        }
    }
    
}

void afisare(){
    for(i=2;i<=n;i++)
    {
        if(d[i]!=INT_MAX)
            cout<<d[i]<<" ";
        else
            cout<<0<<" ";
    }
}

int main(){

    Disjkstra();
    afisare();
    return 0;
}