#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define infinit 100000000000
unsigned long long d[50001],viz[50001],a[5001][5001],tata[50001],start,x,y,z,i,j,n,m,minim,ok,k;
int main()
{
    fin>>n>>m;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            if(i!=j)
            {
                a[i][j]=infinit;
            }
            else
                a[i][j]=0;
        }
    }
    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>z;
        a[x][y]=z;
    }
  start=1;
    minim=infinit;
    viz[start]=1;

    for(i=1; i<=n; i++)
    {
        d[i]=a[start][i];
        tata[i]=start;

    }
    ok=1;
    tata[start]=0;
    while(ok!=0)
    {
        minim=infinit;
        for(i=1; i<=n; i++)
        {
            if(d[i]<minim&&d[i]!=0&&viz[i]==0)
            {
                minim=d[i];
                k=i;
            }
        }
        if(minim!=infinit)
        {
            viz[k]=1;
            for(i=1;i<=n;i++)
            {
                if(viz[i]==0)
                {
                    if(d[k]+a[k][i]<d[i])
                    {
                        d[i]=d[k]+a[k][i];
                        tata[i]=k;
                    }
                }
            }
        }
        else
            ok=0;

    }
for(i=2;i<=n;i++)
    fout<<d[i]<<" ";
    return 0;
}