#include <bits/stdc++.h>
#define nrmax 50002
#define oo (1<<30)
using namespace std;
int D[nrmax];
int n,m,i;
bool inQ[nrmax]={false};
vector< pair <int,int> > G[nrmax];

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

priority_queue <int, vector<int>, cmp> coada;

void citire(){
    int x,y,c;
    ifstream input("dijkstra.in");
input>>n>>m;
for(i=1;i<=m;i++){
        input>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
       }
}

void Dijkstra(){
    int nodCurent,vecin,cost;
    for(i=1;i<=n;i++)D[i]=oo;
    D[1]=0;
    coada.push(1);
    inQ[1]=true;
while(!coada.empty()){
        nodCurent=coada.top();
        coada.pop();
        inQ[nodCurent]=false;
    for(size_t h=0; h<G[nodCurent].size();h++){
        vecin=G[nodCurent][h].first;
        cost=G[nodCurent][h].second;
        if(D[nodCurent]+cost<D[vecin]){
                D[vecin]=D[nodCurent]+cost;
                if(!inQ[vecin]){
                        coada.push(vecin);
                        inQ[vecin]=true;
                }
        }
    }
}
}

void afisare(){
    ofstream print("dijkstra.out");
    for(i=2;i<=n;i++)
            if(D[i]!=oo)print<<D[i]<<" ";
         else print<<"0"<<" ";
}

int main(){
    citire();
    Dijkstra();
    afisare();
    return 0;
}