#include <iostream>
#include <fstream>
using namespace std;
const long long MAXI=999999999999999999;
long long d[50001],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];

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for(i=1;i<=n;i++)d[i]=MAXI;
    nod=1; // aici nodul initial e 1 ,ca asa e in problema de pe infoarena
    viz[nod]=1;
    d[nod]=0;
    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;p[a[i].y]=nod;}
    }
    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=d[i];
                nr=i;
            }
        }

        if(OK==1)
        {
            num++;
            viz[nr]=1;

            for(int j=1;j<=m;j++)
            if(a[j].x==nr&&d[nr]+a[j].c<d[a[j].y])
            {
                d[a[j].y]=d[nr]+a[j].c;
                p[a[j].y]=nr;
            }
        }

    }
    for(i=1;i<=n;i++)if(i!=nod&&d[i]==MAXI)d[i]=0;
    for(i=1;i<=n;i++)if(i!=nod)g<<d[i]<<' ';
    f.close();
    g.close();
}