#include <iostream>
#include <queue>
#include <fstream>
#include <limits.h>

using namespace std;

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

struct Arc{
int nod;
int cost;

    bool operator < (const Arc &x) const
    {
        return cost>x.cost; //Le face automat
    }
};

priority_queue <Arc>pq;
vector<Arc> listaG[50001];
int viz[50001];
int v[50001];

void parcurgere(Arc nod){
    pq.push({1,0});
    v[1] = 0;
    while(!pq.empty()){
        nod = pq.top();
        pq.pop();
        if(viz[nod.nod] == 1){
            continue;
        }
        viz[nod.nod] = 1;
        for(auto muchie : listaG[nod.nod]){ //e nod.nod ca iei partea [int]
            if(muchie.cost + nod.cost< v[muchie.nod]){
                v[muchie.nod] = muchie.cost + nod.cost;
                pq.push({muchie.nod,muchie.cost + nod.cost});
            }
        }
    }
}
int main()
{
    int n,m,n1,n2,c;
    fin>>n>>m;
    for(int i=0;i<m;i++){
        fin>>n1>>n2>>c;
        listaG[n1].push_back({n2,c});
    }

    for(int i=1;i<=n;i++){
        v[i] = INT_MAX;
    }

    Arc x;
    parcurgere(x);

    for(int i = 2;i<=n;i++){
        if(v[i] == INT_MAX){
            v[i] = 0;
        }
        fout<< v[i] << ' ';
    }


}