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

using namespace std;

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

const int NMax=100000;
const int oo=(1<<30);

vector<pair<int,int>>V[NMax];

int D[NMax],N,M;
bool InCoada[NMax];

struct functie{
    bool operator()(int x,int y){
        return D[x]>D[y];
    }
};

priority_queue<int,vector<int>,functie> Q;


void dijkstra(int NodStart){
    for(int i=1;i<=N;i++){
        D[i]=oo;
    }
    D[NodStart]=0;
    Q.push(NodStart);
    InCoada[NodStart]=true;
    while(!Q.empty()){
        int NodCurent=Q.top();
        Q.pop();
        InCoada[NodCurent]=false;
        for(unsigned i=0;i<V[NodCurent].size();i++){
            int Vecin=V[NodCurent][i].first;
            int Cost=V[NodCurent][i].second;
            if(D[NodCurent]+Cost<D[Vecin]){
                D[Vecin]=D[NodCurent]+Cost;
                if(InCoada[Vecin]==false){
                    InCoada[Vecin]=true;
                    Q.push(Vecin);
                }
            }
        }
    }
}
int main()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++){
        int x,y,c;
        fin>>x>>y>>c;
        V[x].push_back(make_pair(y,c));
    }
    dijkstra(1);
    for(int i=2;i<=N;i++){
        if(D[i]==oo){
            fout<<0<<' ';
        }
        else
            fout<<D[i]<<' ';
    }
    fin.close();
    fout.close();
    return 0;
}