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

    Nod *urm;
    Nod *ult;
};
Nod *A[50001];
vector<int> vec;
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;

}
int extrage_din_lista_id_dupa_poz(Nod *nod,int poz)
{
    int p=1;

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


  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();
}

int dijkstra(int s,int v)
{
  dist[s]=0;
    for(int i=1;i<=N;i++)
    {
      if(i!=s)
       dist[i]=(1<<30);
      vec.push_back(i);
    }

    while(!vec.empty())
    {
        int u;
        int Min=(1<<30);
        for(int i=0;i<vec.size();i++)
            if(dist[vec[i]]<Min)
            {
                Min=dist[vec[i]];
                u=vec[i];
            }
        vec.erase(remove(vec.begin(), vec.end(), u), vec.end());
        for(int i=1;i<=N;i++)
        {
            int t=extrage_din_lista_id_dupa_poz(A[u],i);
            if(t>0)
            {
                   int alt=dist[u] + extrage_din_lista_lungime(A[u],t);
                   if(alt<dist[t])
                   {
                     dist[t]=alt;
                   }
            }
            else
             break;
        }

    }

   return dist[v];
}

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

    }
    f.close();
    return 0;
}