#include <fstream>
#include <bitset>
#include <vector>
#define site std::vector<pair<int,int> >::iterator
#define DIM 50002
#define INF 0x3f3f3f3f

using namespace std;

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

int N,M,nr;
vector <pair <int,int> > L[DIM];
vector <int> H(DIM),poz(DIM),D(DIM,INF);
bitset <DIM> inHeap;

int HeapEmpty(){
    return !nr;
}

void up(int x){
    int c=x,p=c/2;

    while(p>=1 && D[H[c]] < D[H[p]]){
        swap(H[p],H[c]);
        swap(poz[H[c]],poz[H[p]]);
        c=p;
        p/=2;
    }

}

void insert(int x){
    H[++nr] = x;
    inHeap[x]=1;
    poz[x]=nr;
    up(nr);
}

void down(int x){
    int p=x,c=2*p;

    while(c<=nr){
        if(c+1<=nr && D[H[c+1]] < D[H[c]])
            c++;
        if(D[H[c]] < D[H[p]]){
            swap(H[p],H[p]);
            swap(poz[H[p]],poz[H[c]]);
            p=c;
            c*=2;
        }
        else
            break;
    }

}

int extractroot(){
    int ans = H[1];
    swap(H[1],H[nr]);
    swap(poz[H[1]],poz[H[nr]]);
    nr--;
    down(1);
    return ans;
}

int main(){

    fin >> N >> M;

    while(M--){
        int x,y,c;

        fin >> x >> y >> c;

        L[x].push_back(make_pair(y,c));

    }

    D[1]=0;
    inHeap[1]=1;

    insert(1);

    while(!HeapEmpty()){
        int node = extractroot();

        for(site it=L[node].begin();it!=L[node].end();it++)
            if(D[it->first] > D[node] + it->second){
                D[it->first] = D[node] + it->second;
                if(inHeap[it->first])
                    up(poz[it->first]);
                else
                    insert(it->first);
            }

    }

    for(int i=2;i<=N;i++)
        if(D[i]!=INF)
            fout << D[i] << " ";
        else
            fout << "0 ";

    fout << "\n";

    fin.close();fout.close();

    return 0;


}