#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
#define nmax 50001
#define inf 0x3f3f3f

using namespace std;

vector < int > gf[nmax], c[nmax];
//multiset<pair<int,int> >   heap;
int n, m, d[nmax] ;


struct comp{
    bool operator () (const pair<int,int> &A, const pair<int,int> &B){
        return d[A.second] > d[B.second];
    }
};

void dijkstra(){
    memset(d, inf, sizeof(d));
    d[1]=0;
    priority_queue<int, vector<pair<int,int> >, comp> heap;
    heap.push(make_pair(0,1));
    while(heap.size()){
        int min = (heap.top()).first;
        int nod = (heap.top()).second;
        //heap.erase(*heap.begin());
        heap.pop();
        for(int i=0; i<gf[nod].size(); ++i){
            int vecin = gf[nod][i];
            int cost_act = c[nod][i];
            if (d[ vecin ] > min + cost_act){
                d[ vecin ] = min + cost_act;
                heap.push(make_pair(d[ vecin ],vecin));
            }
        }
    }

}

int main(){
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;

    for(int i=1; i<=m; i++){
        int x, y, cost;
        f>>x>>y>>cost;
        gf[x].push_back(y);
        c[x].push_back(cost);
    }
    dijkstra();
    for(int i=2; i<=n; i++) if (d[i] >= inf) g<<"0 ";
    else g<<d[i]<<" ";
    return 0;
}