#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;
};

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

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

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

void eliminateFirst(int n){
    int poz=1;
    while(2*poz<=n){
        if(2*poz+1>n || heap[2*poz][0]<heap[2*poz+1][0]){
            heap[poz][0]=heap[2*poz][0];
            heap[poz][1]=heap[2*poz][1];
            poz*=2;
        }
        else{
            heap[poz][0]=heap[2*poz+1][0];
            heap[poz][1]=heap[2*poz+1][1];
            poz=poz*2+1;
        }
    }
}

void addNew(int poz,int n){
    heap[n+1][1]=poz;
    heap[n+1][0]=v[poz].min_dist;

    int i=n+1,aux;
    while(i/2>=1 && heap[i/2][0]>heap[i][0]){
        aux=heap[i][0];
        heap[i][0]=heap[i/2][0];
        heap[i/2][0]=aux;

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

        i/=2;
    }
}

int searchPosition(int poz){
    int i=1;
    while(heap[i][1]!=poz) i++;
    return i;
}

void moveUp(int i){
    int aux;
    while(i/2>=1 && heap[i/2][0]>heap[i][0]){
        aux=heap[i][0];
        heap[i][0]=heap[i/2][0];
        heap[i/2][0]=aux;

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

        i/=2;
    }
}

void evaluate(int n){
    heap[1][0]=0; /*distanta*/
    heap[1][1]=1; /*pozitia lui in vector*/

    int nr=1;
    int poz,poz2;
    int i,j;
    while(nr>0 && n>=0){
        poz=heap[1][1]; /*luam cel mai mic element*/
        v[poz].visited=1;
        eliminateFirst(nr); /*eliminam cel mai mic element din heap*/
        nr--;

        for(i=0;(unsigned int)i<v[poz].connections.size();i++){
            poz2=v[poz].connections[i];
            if(v[poz2].visited==0){
                if(v[poz2].min_dist>v[poz].min_dist+v[poz].distances[i]){
                    if(v[poz2].min_dist<INF){
                        j=searchPosition(poz2); /*cautam pozitia pe care am mai pus in vector*/
                        v[poz2].min_dist=v[poz].min_dist+v[poz].distances[i]; /*actualizam suma*/
                        heap[j][0]=v[poz2].min_dist;
                        moveUp(j);
                    }
                    else{
                        v[poz2].min_dist=v[poz].min_dist+v[poz].distances[i]; /*actualizam suma*/
                        addNew(poz2,nr);
                        nr++;
                    }
                }
            }
        }

        n--;
    }
}

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[b].connections.push_back(a);
        v[a].distances.push_back(c);
        v[b].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;
}