#include <iostream>
#include <fstream>
using namespace std;
int n,m,r,s[503],mn,c[503][503],t[503],d[503];
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int main()
{
    int h,i,j,nr,k;
    fin>>n>>m;
    r=1;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
            if (i!=j) c[i][j]=10000000;
    }
    for (h=1;h<=m;h++)
    {
        fin>>i>>j>>nr;
        c[i][j]=nr;
    }
    s[r]=1;
    for (i=1;i<=n;i++)
        if (i!=r)
        {
            d[i]=c[r][i];
            t[i]=r;
        }
    d[r]=0;
    t[r]=0;
    for (k=1;k<n;k++)
    {
        mn=10000000;
        for (j=1;j<=n;j++)
        {
            if ((mn>d[j]&&s[j]==0))
            {
                i=j;
                mn=d[j];
            }
        }
        s[i]=1;
        for (j=1;j<=n;j++)
        {
            if (d[j]>(d[i]+c[i][j]))
            {
                d[j]=d[i]+c[i][j];
                t[j]=i;
            }
        }
    }
    for (i=2;i<=n;i++)
        fout<<d[i]<<" ";
    fin.close();
    fout.close();
    return 0;
}