#include <fstream>
#include <list>
#define DIM 500001
#define INF 9999999

using namespace std;
int n,m,x,y,c,H[DIM],d[DIM],hp;
bool v[DIM];

list<pair<int,int> > nod[DIM];

void addHeap(int k)
{
    H[++hp]=k;
    int q=hp;
    while(d[H[q]]<d[H[q/2]] && q>1)
    {
        swap(H[q],H[q/2]);
        q=q/2;
    }
}
void delHeap(int k)
{
    H[k]=H[hp];
    --hp;
    int q=hp;
    while(d[H[q]]<d[H[q/2]] && q>1)
    {
        swap(H[q],H[q/2]);
        q=q/2;
    }
    while((d[H[q]] > d[H[q*2]] || d[H[q]] > d[H[q*2+1]]) && q*2<=hp)
    {
        if(d[H[q*2]] <d[H[q*2+1]] || q*2+1>hp)
        {
            swap(H[q], H[q*2]);
            q=q*2;
        }
        else if(2*q+1<=hp)
        {
            swap(H[q],H[q*2+1]);
            q=q*2+1;
        }
    }
}

void dijkstra(int k)
{
    addHeap(k);
    while(hp!=0)
    {
        int vf=H[1];
        delHeap(1);
        for(list<pair<int,int> >::iterator i=nod[vf].begin();i!=nod[vf].end();++i)
        {
            std::pair<int,int> z=*i;
            if(!v[z.first])
            {
                addHeap(z.first);
                d[z.first]=d[vf]+z.second;
                v[z.first]=1;
            }
        }
    }
}

int main()
{
    FILE *f=fopen("dijkstra.in","r");
    FILE *g=fopen("dijkstra.out","w");
    fscanf(f,"%d %d",  &n,&m);
    for(int i=1;i<=m;++i)
    {
        fscanf(f,"%d %d %d", &x,&y,&c);
        nod[x].push_back(make_pair(y,c));
        nod[y].push_back(make_pair(x,c));
    }
    for(int i=2;i<=n;++i)
    d[i]=INF;
    dijkstra(1);
    for(int i=2;i<n;++i)
    {
        if(d[i]==INF)
        fprintf(g,"0 ");
        else
        fprintf(g,"%d ",d[i]);
    }
    if(d[n]==INF)
    fprintf(g,"0\n");
    else
    fprintf(g,"%d\n",d[n]);
    fprintf(g,"\n");
    fclose(f);
    fclose(g);
    return 0;
}