#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <memory.h>
#define oo 2*(10e9)

using namespace std;
struct nod {
             int cost;
             int inf;
             nod *next;
            }*prim[10001],*aux,*p;

 FILE *fin=fopen("djikstra.in","r");


int main()
{

       int n, m, X, Y, C;
        fscanf(fin,"%d%d",&n,&m);
    for(int i =1;i <=m ;i++)
        {
         fscanf(fin,"%d%d%d",&X,&Y,&C);
       if(X!=Y)
         {
         aux=new nod;
         aux->cost=C;
         aux->inf=X;
         aux->next=prim[Y];
         prim[Y]=aux;

         aux=new nod;
         aux->cost=C;
         aux->inf=Y;
         aux->next=prim[X];
         prim[X]=aux;
         }
        }

    int d[128],pred[128],viz[128];
    memset(viz,0,sizeof(viz));

    for(int i=1;i<=n;i++)d[i]=oo;
    d[1]=0;
  int con=0,min,dmin;

  while(con<n)
  {
   dmin=oo;con++;
   for(int i=1;i<=n;i++) if(d[i]<dmin && viz[i]==0) {min=i;dmin=d[i];}
    viz[min]=1;
    for(p=prim[min];p;p=p->next)
        if (d[p->inf]>d[min]+p->cost)
                {d[p->inf]=d[min]+p->cost;
                 pred[p->inf]=min;
                }
  }
  for(int i=1;i<=n;i++)
    cout<<d[i]<<" ";
/**
int n=10,vect[123];

for(int i=1;i<=n;i++)
    fscanf(fin,"%d",&vect[i]);

  vector<int> v(vect,vect+n+1);

  make_heap (v.begin(),v.end());
  cout << "initial max heap   : " << v.front() << '\n';

  pop_heap (v.begin(),v.end());v.pop_back();
  cout << "max heap after pop : " << v.front() << '\n';

  v.push_back(123); std::push_heap (v.begin(),v.end());
  cout << "max heap after push: " << v.front() << '\n';

  sort_heap (v.begin(),v.end());

  cout << "final sorted range :";
    for (int  i=1; i<=n; i++)
     cout << ' ' << v[i];
*/

    return 0;
}