#include <fstream>
#include <vector>
#define NMAX 50002
#define INF 10000000;
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct muchie {int vf,cost;};
vector <muchie> L[NMAX];
void citire();
void initializare();
void dijkstra(int x);
int n,Cmin[NMAX],M[NMAX],m;
int main()
{
    citire();
    initializare();
    dijkstra(1);
}
void citire()
{
    int a,b,c,i;
    muchie aux;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        aux.vf=b;aux.cost=c;
        L[a].push_back(aux);
    }
}
void initializare()
{
    int i;
    for(i=1;i<=n;i++) Cmin[i]=INF;
    M[1]=1;Cmin[1]=0;
    for(i=0;i<L[1].size();i++)
        Cmin[L[1][i].vf]=L[1][i].cost;
}
void dijkstra(int x)
{
    int i,j,vfmin,minim;
    for(i=1;i<n;i++)
    {
        minim=INF+1;
        for(j=1;j<=n;j++)
            if(Cmin[j]<minim&&M[j]==0)
                {
                    minim=Cmin[j];
                    vfmin=j;
                }
        M[vfmin]=1;
        for(j=0;j<L[vfmin].size();j++)
            if(Cmin[L[vfmin][j].vf]>Cmin[vfmin]+L[vfmin][j].cost)
                Cmin[L[vfmin][j].vf]=Cmin[vfmin]+L[vfmin][j].cost;
    }
   for(i=2;i<=n;i++)
   {
       if (Cmin[i]==10000000)
          fout<<0<<" ";
      else
            fout<<Cmin[i]<<" ";
   }
}