#include <iostream>
#include <fstream>
#define inf 999999999
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int x, dist, y, m, n, R, s[30000], t[30000], d[30000];
int a[20000][20000];
int verif()
{
    for(int i=1;i<=n;i++)
    {
        if(s[i]==0&&d[i]!=inf)
            return 1;
    }
    return 0;
}
int cauta()
{
    int xmin=9999999, poz=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i]<xmin&&s[i]==0)
        {
            xmin=d[i];
            poz=i;
        }
    }
    return poz;
}
int main()
{
    fin>>n>>m;
    R=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            a[i][j]=inf;
        }
        d[i]=inf;
    }
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>dist;
        a[x][y]=dist;
        if(x==1)
        {
            d[y]=dist;
            t[y]=1;
        }
    }
    s[1]=1;
    int k=1;
    while(verif())
    {
        k=cauta();
        for(int i=1;i<=n;i++)
        {
            if(d[i]>d[k]+a[k][i]&&a[k][i]!=inf)
            {
                d[i]=d[k]+a[k][i];
                t[i]=k;
            }
        }
        s[k]=1;
    }
    for(int i=2;i<=n;i++)
    {
        fout<<d[i]<<' ';
    }
    fin.close();
    fout.close();
    return 0;
}