#include<iostream>
#include<fstream>
using namespace std;
int N,M;
int viz[50001];
struct Nod
{
    int lungime;
    int id;

    Nod *urm;
    Nod *ult;
};
Nod *A[50001];
void adauga_in_lista(Nod *&nod,int id,int lungime)
{
        Nod *p=new Nod;
        p->id=id;
        p->lungime=lungime;
        p->urm=nod;
        nod=p;
}
bool exista_in_lista_id(Nod *nod,int id)
{

      while(nod!=0)
      {
          if(nod->id==id)
              return true;
          nod=nod->urm;
      }


  return false;

}
int extrage_din_lista_lungime(Nod *nod,int id)
{

      while(nod!=0)
      {
          if(nod->id==id)
              return nod->lungime;
          nod=nod->urm;
      }


  return -1;

}


void citeste(const char* nume)
{
  ifstream f(nume);
  f>>N;
  f>>M;
  int j,k,c;
  for(int i=1;i<=M;i++)
    {
        f>>j;
        f>>k;
        f>>c;
       adauga_in_lista(A[j],k,c);
    }
  f.close();
}
void clearViz(int n)
{
    for(int i=1;i<=n;i++)
        viz[i]=0;
}
int dijkstra(int s,int v)
{
    int min=(1<<30);
    int t;
   if(s==v)
      return 0;
   for(int i=v;i>s;i--)
   {
       if(exista_in_lista_id(A[s],i) && viz[i]==0)
       {
            viz[i]=1;
            t= extrage_din_lista_lungime(A[s],i) +dijkstra(i,v);
            if(t<min)
                min=t;
       }
   }
   return min;
}

int main()
{
    citeste("dijkstra.in");
    ofstream f("dijkstra.out");
    for(int i=2;i<=N;i++)
    {
       int val=0;
       val=dijkstra(1,i);
       if(val == (1<<30))
         f<<0<<" ";
       else
        f<<val<<" ";

       clearViz(N);
    }
    f.close();
    return 0;
}