#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define usi unsigned short int
#define Inf 2000000000
using namespace std;

int N, M;

struct comp{
    bool operator()(pair<usi, int> &a, pair<usi, int> &b){
        return a.second > b.second;
    }
};
vector< vector< pair<usi, int> > > A;
vector<int> d;

void initializare()
{
    int x, y, c;
    scanf("%d%d", &N, &M);
    A.resize(N+1);

    for(int i=1; i<=M; i++){
        scanf("%d%d%d", &x, &y, &c);
        A[x].push_back(make_pair(y, c));
    }
}

void Dijkstra(int nodStart)
{
    int vec, cost, nOptim;
    priority_queue<int, vector< pair<usi, int> >, comp> C;
    d.assign(N+2,Inf);
    d[nodStart]=0;
    C.push(make_pair(nodStart, 0));
    while(!C.empty()){
        nOptim=C.top().first;
        C.pop();
        for(int i=0; i<A[nOptim].size(); i++)
        {
            //pentru fiecare nod pentru care exista muchie din nOptim in acel nod
            vec = A[nOptim][i].first;
            cost = A[nOptim][i].second;

            if( d[vec] > d[nOptim] + cost)
            {
                //daca putem imbunatati costul drumului din nodStart in vecinul nodului optim prin nOptim
                d[vec] = d[nOptim] + cost;
                C.push(make_pair(vec, d[vec])); // adauga vecinul in coada cu prioritate
            }
        }
    }
    vector< vector<pair<usi, int> > >().swap(A);      //erase
}

int main()
{
    freopen("dijkstra.in","rt",stdin);
    freopen("dijkstra.out","wt",stdout);
    initializare();
    Dijkstra(1);

    for(int i=2; i<=N; i++)
        cout<<(d[i] == Inf ? 0 : d[i] )<<' ';
    cout<<'\n';
}