#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,x,y,c,i,j,u,m;
int lista[1000][1000];
int cost[1000][1000];
int d[1000];
int q[1000];
int index;
bool viz[1000];

void citire()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
        d[i]=100000;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        lista[x][0]++;
        lista[y][0]++;
        lista[x][lista[x][0]]=y;
        cost[x][lista[x][0]]=c;
        lista[y][lista[y][0]]=x;
        cost[y][lista[y][0]]=c;
        if(x==1)
        {
            d[y]=c;
            index++;
            q[index]=y;
        }
        else if(y==1)
        {
            d[x]=c;
            index++;
            q[index]=x;
        }
    }
}

void sortarecoada()
{
    for(i=2;i<=index;i++)
    {
        while(d[q[i]]<d[q[i-1]])
        {
            j=q[i-1];
            q[i-1]=q[i];
            q[i]=j;
        }
    }
}

void Dijkstra()
{
    sortarecoada();
    while(index!=0)
    {
        u=q[1];
        viz[u]=1;
        for(i=1;i<=lista[u][0];i++)
        {
            if(viz[lista[u][i]]==0 && d[lista[u][i]]>d[u]+cost[u][i])
            {
                d[lista[u][i]]=d[u]+cost[u][i];
                for(j=2;j<index;j++)
                    q[j-1]=q[j];
                index++;
            }
        }
        index--;
    }
}

void afisare()
{
    for(i=2;i<=n;i++)
    {
        if(d[i]!=100000)
            g<<d[i]<<" ";
        else
            g<<0<<" ";
    }
}

int main()
{
    citire();
    Dijkstra();
    afisare();
    f.close();
    g.close();
    return 0;
}