#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int INF = 1000000001;

struct node{
    vector <int> distances;
    vector <int> next;
    int visited;
};
node v[50001]; /*vectorul de noduri*/
int final_array[50001]; /*rezultatul final*/
int heap[50001]; /*heapul care are pozitiile in vectorul de noduri*/
int poz_heap[50001]; /*unde se afla fiecare nod in heap*/
int val_heap[50001]; /*lungimea distantei fiecarui nod in heap*/
int n_heap;

void init(int n){
    int i;
    for(i=1;i<=n;i++){
        heap[i]=i;
        poz_heap[i]=i;
        val_heap[i]=INF;
        v[i].visited=0;
    }
    n_heap=n;
}

void upheap(int x){
    int aux;
    while(x/2>0 && val_heap[x]<val_heap[x/2]){
        aux=heap[x];
        heap[x]=heap[x/2];
        heap[x/2]=aux;

        aux=val_heap[x];
        val_heap[x]=val_heap[x/2];
        val_heap[x/2]=aux;

        poz_heap[heap[x]]=x;
        poz_heap[heap[x/2]]=x/2;

        x/=2;
    }
}

void downheap(int x){
    int aux,y=0;
    while(x!=y){
        y=x;
        if(y*2<=n_heap && val_heap[x]>val_heap[y*2]) x=y*2;
        if(y*2+1<=n_heap && val_heap[x]>val_heap[y*2+1]) x=y*2+1;

        aux=heap[x];
        heap[x]=heap[y];
        heap[y]=aux;

        aux=val_heap[x];
        val_heap[x]=val_heap[y];
        val_heap[y]=aux;

        poz_heap[heap[x]]=x;
        poz_heap[heap[y]]=y;
    }
}

void completeDistances(int poz,int n){
    int i,poz2;

    v[poz].visited=1;
    final_array[poz]=val_heap[poz_heap[poz]];
    if(final_array[poz]==INF) final_array[poz]=0;

    if(n_heap<=1 || heap[1]==INF) return;

    for(i=0;(unsigned int)i<v[poz].distances.size();i++){
        if(v[v[poz].next[i]].visited==0){
            poz2=poz_heap[v[poz].next[i]]; /*pozitia in heap a urmatorului element*/
            if(val_heap[poz2]>final_array[poz]+v[poz].distances[i]){
                val_heap[poz2]=final_array[poz]+v[poz].distances[i];
                upheap(poz2);
            }
        }
    }
    heap[1]=heap[n_heap];
    val_heap[1]=val_heap[n_heap];
    n_heap--;
    poz_heap[heap[1]]=1;
    if(n_heap>1) downheap(1);

    completeDistances(heap[1],n);
}

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

    int n,m;
    fin>>n>>m;

    init(n);

    int i;
    int a;
    int b;
    int c;
    for(i=0;i<m;i++){
        fin>>a>>b>>c;
        v[a].next.push_back(b);
        v[a].distances.push_back(c);
    }

    val_heap[1]=0;
    completeDistances(1,n);

    for(i=2;i<=n;i++)
        fout<<final_array[i]<<' ';
    fout<<endl;

    fin.close();
    fout.close();
    return 0;
}