#include<iostream>
#include<fstream>
#include<vector>
#include<list>
#include<limits.h>
using namespace std;
struct nod{
int cost;
int visited;
int marked;
vector<nod*> next;
vector<int> dist;};
class heap{
    public:
        void add(nod*x);
        nod*min();
        int empty(){return (heap.size()==0);}
    private:
        vector<nod*>heap;
        int p(int pos){return ((pos-1)/2);}
        int l(int pos){return (pos*2+1);}
        int r(int pos){return (pos*2+2);}
        int e(int pos){return (pos<(int)heap.size());}
        int f(int pos){return (e(l(pos))&&e(r(pos)));}};
void heap::add(nod*x){
    int pos=(int)heap.size();
    nod*aux;
    heap.push_back(x);
    while(pos>0&&heap[pos]->cost<heap[p(pos)]->cost){
        aux=heap[pos];
        heap[pos]=heap[p(pos)];
        heap[p(pos)]=aux;
        pos=p(pos);}}
nod*heap::min(){
    int max,j;
    nod*ret=heap[0];
    nod*aux=heap[heap.size()-1];
    heap[heap.size()-1]=heap[0];
    heap[0]=aux;
    heap.pop_back();
    j=0;
    max=0;
    while(max!=-1){
        max=-1;
        if(e(l(j)))max=l(j);
        if(e(r(j))&&heap[l(j)]->cost<heap[r(j)]->cost)max=r(j);
        if(max!=-1&&heap[j]->cost>heap[max]->cost){
            aux=heap[j];
            heap[j]=heap[max];
            heap[max]=aux;}}
    return ret;}
void dijkstra(vector<nod*> graf,nod* start){
    heap*set=new heap;
    list<nod*>::iterator i_min;
    nod*cur;
    int min;
    for(int i=0;i<(int)graf.size();i++){graf[i]->cost=INT_MAX;graf[i]->visited=graf[i]->marked=0;}
    set->add(start);
    start->cost=0;
    while(!set->empty()){
        min=INT_MAX;
        cur=set->min();
        cur->visited=1;
        for(int i=0;i<(int)cur->next.size();i++)
        if(cur->dist[i]+cur->cost<cur->next[i]->cost){
            cur->next[i]->cost=cur->dist[i]+cur->cost;
            if(cur->next[i]->visited==0&&cur->next[i]->marked==0){
                set->add(cur->next[i]);
                cur->next[i]->marked=1;}}}}
int main(){
    int n,m,d1,d2,d3;
    vector<nod*> graf;
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for(int i=0;i<n;i++)graf.push_back(new nod);
    for(int i=0;i<m;i++){
        f>>d1>>d2>>d3;
        graf[d1-1]->next.push_back(graf[d2-1]);
        graf[d1-1]->dist.push_back(d3);}
    dijkstra(graf,graf[0]);
    for(int i=1;i<n;i++)
        if(graf[i]->cost!=INT_MAX)g<<graf[i]->cost<<' ';
        else g<<"0 ";
    f.close();g.close();
    return 0;}