#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;

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

struct graf{
int nod;
int dist;
graf* next;
};

int n,m;
graf* v[100000];
int tent[100000];
int infty=2000000000;

int minHeap[200010];
int poz[100010];

int len = 0;
void print();

int compare(int x, int y)
{
        return tent[x] > tent[y];
}

void upHeap(int k){
    int aux;

    while(k!=1&&compare(minHeap[k/2],minHeap[k])){
        aux = minHeap[k/2];
        minHeap[k/2] = minHeap[k];
        minHeap[k] = aux;
        poz[minHeap[k]] = k;
        poz[minHeap[k/2]] = k/2;


        k=k/2;
    }
}

void downHeap(int k){
int aux,t;
 while((compare(minHeap[k],minHeap[2*k])||compare(minHeap[k],minHeap[2*k+1]))){
        if(compare(minHeap[2*k+1],minHeap[2*k]))
            t=2*k;
        else
            t=2*k+1;

        if(t>len)
            break;
        aux = minHeap[t];
        minHeap[t] = minHeap[k];
        minHeap[k] = aux;
        poz[minHeap[k]] = k;
        poz[minHeap[t]] = t;

        k=t;
    }
}

void add(int a){
    len = len + 1;
    int k = len;

    minHeap[k]=a;
    poz[a]=k;

    upHeap(k);
}

void pop(){
    int k = 1;
    minHeap[k] = minHeap[len];
    poz[minHeap[len]] = 0;
    minHeap[len] = 0;
    --len;

    downHeap(k);
}






void add(int a, int b, int cost)
{
    graf* q = new graf;
    q->nod  = b;
    q->dist = cost;
    q->next = v[a];
    v[a] = q;
}

void print();

void visit(int current,int distance){
    graf* p=v[current];
    while(p){
        if(tent[p->nod]>distance+p->dist){

            tent[p->nod]=distance+p->dist;

            if(poz[p->nod])
            upHeap(poz[p->nod]);
        }
        p=p->next;
    }
}

void print(){
    int i;
for(i=1;i<=len;++i)
cout << tent[minHeap[i]]<< " ";

cout <<"\n";
for(i=1;i<=len;++i)
cout << poz[minHeap[i]]<< " ";

cout <<"\n";
}



int main()
{
    int i,x,y,z;
    int distance = 0;

    fin >> n >> m;
    for (i=1;i<=m;++i){
        fin >> x >> y >> z;
        add(x,y,z);
    }
    for (i=2;i<=n;++i)
        tent[i]=infty;
    tent[0]=infty;

    for (i=2;i<=n;++i)
        add(i);

    visit(1,0);

    while(len > 0 && tent[minHeap[1]]!=infty)
    {
        distance = tent[minHeap[1]];
        y = minHeap[1];
        pop();

        visit(y,distance);

    }

    if(tent[minHeap[1]]==infty&&len!=0)
        for(i=1;i<=len;++i)
            tent[minHeap[i]]=0;


        for (i=2;i<=n;++i)
            fout << tent[i] << " ";

    return 0;
}