#include <iostream>
#include <fstream>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m,x,y,z,i,j,k,ok,minn;
int a[5000][5000],viz[5000],v[5000],tata[5000];

int main()
{

    f>>n>>m;
    for (i=1;i<=m;i++){f>>x>>y>>z; a[x][y]=z;}

    for (i=1;i<=n;i++)
     for (j=1;j<=n;j++)
       {
           if (a[i][j]==0)
           {a[i][j]=9999;}
       }

    for (i=1;i<=n;i++)
    {
        v[i]=a[1][i];
        tata[i]=1;
    }

    tata[1]=0;ok=1;viz[1]=1;
    while(ok==1)
    {
        minn=9999;
        for (i=1;i<=n;i++)
            if (v[i]<minn && viz[i]==0)
            {
                minn=v[i];
                k=i;
            }

        if (minn!=9999)
        {
            viz[k]=1;
            for (i=1;i<=n;i++)
            {
                if (a[k][i]+minn<v[k] && a[k][i]!=9999)
                {
                    v[k]= a[k][i]+minn;
                    tata[i]=k;
                }
            }
        }
        else
        ok=0;
    }

    for (i=2;i<=n;i++)
    {
        if (v[i]==9999)
        {
          g<<0<<" ";
        }
        else
        {
          g<<v[i]<<" ";
        }
    }


}