#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
#include <memory.h>
#define oo 5000

using namespace std;

vector < pair <int,int> >adj[123];

int N,M,D[123];
 FILE *fout=fopen ("dijkstra.out","w");

void dijkstra(int start)
{

    for(int i=0;i<N;i++) D[i]=oo;
        D[start]=0;
        set<pair<int,int> >pq;  //creare coada
        pq.insert(make_pair(0,start)); //inserare startul in coada

        while(!pq.empty())
        {
            int node=pq.begin()->second; //selectez nodul curent ca a doua val din coada
            pq.erase(pq.begin());        //scot nodul curent din coada

            for(int i=0;i < (int)(adj[node].size()); i++) //parcurg toti vecinii lui nodc prin adj[node]
                {
                    if(D[node]+adj[node][i].second >= D[adj[node][i].first]) continue; // compar daca distanta de la
                                                                                      // node+costul pana in adj[node][i].second
                                                                                      // <= distanta curenta de la node la adj[node][i].first
          //daca e
                    if(D[adj[node][i].first] < oo)//il scot din coada
                        pq.erase(pq.find(make_pair(D[adj[node][i].first], adj[node][i].first)));//il scot din coada

                    D[adj[node][i].first] = D[node] + adj[node][i].second; //actualizez distanta
                    pq.insert( make_pair ( D[adj[node][i].first] , adj[node][i].first)); //pun in coada distanta si nodul

                }
        }
        for(int i=0;i<N;i++)
            {if(i!=start)fprintf (fout,"%d ", D[i] == oo ? 0 : D[i]);
            }
}

int main()
{
    int x,y,c;

    FILE *fin= fopen("dijkstra.in","r");
        fscanf (fin,"%d%d",&N,&M);
    for(int i=0;i<M;i++)
        {fscanf (fin,"%d%d%d",&x,&y,&c);
        x--;y--;
         adj[x].push_back(make_pair(y,c));
        }



    dijkstra(0);

    return 0;
}

/**
struct nod {
             int cost;
             int inf;
             nod *next;
            }*prim[50001],*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[50001],pred[50001],viz[50001];
    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;
}
*/