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

using namespace std;

const int INF=1000000001;

struct vertex{
    vector <int> connections;
    vector <int> distances;

    char visited;
    int min_dist;
    int poz_heap;
};

vertex v[50001];
int heap[50001][2];

void init(int n){
    v[1].visited=0;
    v[1].poz_heap=1;
    heap[1][0]=0;
    heap[1][1]=1;

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

void downHeap(int poz,int n){
    int aux,flag=0;
    while(2*poz<=n && flag==0){
        if(2*poz+1>n && heap[poz][0]>heap[2*poz][0]){
            aux=heap[poz][0];
            heap[poz][0]=heap[2*poz][0];
            heap[2*poz][0]=aux;

            aux=heap[poz][1];
            heap[poz][1]=heap[2*poz][1];
            heap[2*poz][1]=aux;

            poz=2*poz;
        }
        else if(heap[2*poz][0]>heap[2*poz+1][0] && heap[poz][0]>heap[2*poz+1][0]){
            aux=heap[poz][0];
            heap[poz][0]=heap[2*poz+1][0];
            heap[2*poz+1][0]=aux;

            aux=heap[poz][1];
            heap[poz][1]=heap[2*poz+1][1];
            heap[2*poz+1][1]=aux;

            poz=2*poz+1;
        }
        else if(heap[2*poz][0]<heap[2*poz+1][0] && heap[poz][0]>heap[2*poz][0]){
            aux=heap[poz][0];
            heap[poz][0]=heap[2*poz][0];
            heap[2*poz][0]=aux;

            aux=heap[poz][1];
            heap[poz][1]=heap[2*poz][1];
            heap[2*poz][1]=aux;

            poz=2*poz;
        }
        else{
            flag=1;
        }
    }
}

void upHeap(int poz,int n){
    int aux;
    while(poz/2>=1 && heap[poz/2][0]>heap[poz][0]){
        v[heap[poz][1]].poz_heap=poz/2;
        v[heap[poz/2][1]].poz_heap=poz;

        aux=heap[poz][0];
        heap[poz][0]=heap[poz/2][0];
        heap[poz/2][0]=aux;

        aux=heap[poz][1];
        heap[poz][1]=heap[poz/2][1];
        heap[poz/2][1]=aux;

        poz/=2;
    }
}

void evaluate(int n){
    int nr=n;
    int poz,poz2;
    int i;
    while(nr>0 && heap[1][0]!=INF){
        poz=heap[1][1]; /*luam cel mai mic element*/
        v[poz].visited=1;
        v[poz].min_dist=heap[1][0];
        nr--;
        heap[1][0]=heap[nr+1][0];
        heap[1][1]=heap[nr+1][1];
        downHeap(1,nr); /*eliminam cel mai mic element din heap*/

        for(i=0;(unsigned int)i<v[poz].connections.size();i++){
            poz2=v[poz].connections[i];
            if(v[poz2].visited==0){
                if(heap[v[poz2].poz_heap][0]>v[poz].min_dist+v[poz].distances[i]){
                    heap[v[poz2].poz_heap][0]=v[poz].min_dist+v[poz].distances[i];
                    upHeap(v[poz2].poz_heap,nr);
                }
            }
        }
    }
}

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

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

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

    init(n);
    evaluate(n);

    for(i=2;i<=n;i++){
        if(v[i].min_dist!=INF)
            fout<<v[i].min_dist<<" ";
        else
            fout<<"0 ";
    }
    fout<<endl;

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