#include <bits/stdc++.h>
#define nmax 50002
using namespace std;
const int INF = 0x3f3f3f3f;

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

vector<pair<int,int>> G[nmax];
set <pair<int,int>> S;
int N,M,V[nmax];

void Dks(int nod){
    memset(V,INF,sizeof(V));
    V[nod]=0;
    S.insert({0,nod});
    while(!S.empty()){
        int n=S.begin()->second,d=S.begin()->first;
        S.erase(S.begin());
        for(vector<pair<int,int>>::iterator it=G[n].begin();it!=G[n].end();it++){
            int to=it->first,dd=it->second;
            if(d+dd<V[to]){
                if(V[to]!=INF)S.erase(S.find({V[to],to}));
                V[to]=d+dd;
                S.insert({V[to],to});
            }
        }
    }
}

int main()
{
    int a,b,c;
    fin>>N>>M;
    for(int i=1;i<=M;++i){
        fin>>a>>b>>c;
        G[a].push_back({b,c});
    }
    Dks(1);
    for(int i=2;i<=N;++i)
        fout<<((V[i]==INF)?0:V[i])<<' ';
    fout<<endl;
    return 0;
}