#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int numax=20005;

struct data{

int val;

int poz;
}x;

vector <data> citire[50005];

vector<data> w(1);
vector<data> ::iterator it;

data wfinal[50005];

void schimbare(int a,int b)
{

    wfinal[w[a].poz].poz=b;
    wfinal[w[b].poz].poz=a;


    data aux=w[a];

    w[a]=w[b];
    w[b]=aux;



}

int minimul(int a,int b)
{
    if(a<b)
        return a;

    return b;

}



void introducere(data a, int cost_initial)
{
    int j;

    data b= a;
    b.val= b.val + cost_initial;


    if(wfinal[a.poz].val==numax)
    {
         w.push_back(b);
         j=w.size()-1;
         wfinal[b.poz].val=b.val;
         wfinal[b.poz].poz=w.size()-1;


         while(w[j].val<w[j/2].val&&j>1)
         {
             schimbare(j,j/2);

             j=j/2;
         }



    }
    else
    {
        j=wfinal[b.poz].poz;
        wfinal[b.poz].val=b.val;

        w[j].val=b.val;

        while(w[j].val<w[j/2].val)
        {
            schimbare(j,j/2);

            j=j/2;
        }



    }




}

int stergere()
{
    int returnare=w[1].poz,minim,i;
    data sfarsit=w[w.size()-1];


    if(w.size()==1)
        return 0;

    wfinal[returnare].poz=0;
    wfinal[sfarsit.poz].poz=1;

    w[1]=sfarsit;

    i=1;
    w.pop_back();

    if(w.size()==2||w.size()==1)
        return returnare;


    if(w.size()-1>i*2+1)
        minim=minimul(w[i*2].val,w[i*2+1].val);
    else
        minim=w[i*2].val;


    while(w[i].val>minim&&i<w.size()-1)
    {
        if(w.size()-1<i*2+1)
        {
            schimbare(i,i*2);
            i=i*2;
            continue;
        }


        if(w[i*2].val<w[i*2+1].val)
        {
            schimbare(i,i*2);
            i=i*2;

        }
        else
        {
            schimbare(i,i*2+1);
            i=i*2+1;
        }

        if(w.size()-1>i*2+1)
            minim=minimul(w[i*2].val,w[i*2+1].val);
        else
            minim=w[i*2].val;

    }


    return returnare;

}


int functie(int a)
{
    int i,cost_init=wfinal[a].val;

    for(i=0;i<citire[a].size();i++)
    {
        int x=citire[a][i].val;
        int j=citire[a][i].poz;

        if(x+cost_init < wfinal[j].val)
        {
            introducere(citire[a][i],cost_init);
        }



    }

    citire[a].clear();
    citire[a].shrink_to_fit();


    return stergere();

}


int main()
{
    int n,m,i,a,b,c;

    fin>>n>>m;

    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;

        x.val=c;
        x.poz=b;
        citire[a].push_back(x);
        x.poz=a;
        citire[b].push_back(x);


    }


    for(i=2;i<=n;i++)
        wfinal[i].val=numax;

    i=1;

    while(i!=0)
        i=functie(i);


   for(i=2;i<=n;i++)
       fout<<wfinal[i].val<<" ";


    return 0;
}