#include <iostream>
#include <fstream>
using namespace std;
const long long MAXI=999999999999999999;
long long d[5001],maxi;
int p[50001],viz[50001],n,m,i,j,OK,nod,nr,num=1;
struct ev
{
    int x,y;
    long long c;
};
ev a[250001];

void dijkstra(int i)
{
    for(int j=1;j<=m;j++)
    {
        if(a[j].x==i&&viz[j]==0)
        {
            if(d[i]+a[j].c<d[a[j].y])d[a[j].y]=d[i]+a[j].c;
        }
        if(a[j].y==i&&viz[j]==0)
        {
            if(d[i]+a[j].c<d[a[j].x]){d[a[j].x]=d[i]+a[j].c;cout<<i;}
        }
    }
}

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for(i=1;i<=n;i++)d[i]=MAXI;
    nod=1;
    viz[nod]=1;
    for(i=1;i<=m;i++)
    {
        f>>a[i].x>>a[i].y>>a[i].c;
        if(a[i].x==nod)d[a[i].y]=a[i].c;
        if(a[i].y==nod)d[a[i].x]=a[i].c;
    }
    OK=1;
    while(OK&&num<n)
    {
        OK=0;maxi=MAXI;
        for(i=1;i<=n;i++)
        {
            if(d[i]<maxi&&viz[i]==0)
            {
                OK=1;
                maxi=a[i].c;
                nr=i;
            }
        }
        viz[nr]=1;num++;
        dijkstra(nr);
    }
    for(i=1;i<=n;i++)if(i!=nod)g<<d[i]<<' ';
    f.close();
    g.close();
}