#include <iostream>
#include <fstream>
#include <set>
#include <algorithm>
#include <vector>
#define inf 1<<30
#define nmax 50001
#define ind second
using namespace std;

vector <int> vecin[nmax],muchie[nmax];
bool vizitat[nmax];
set <pair<int, int> > q;
int best[nmax],m,n,a,b,c,i;
void dijkstra()
    {
        pair <int,int> nod;
        int curent,costcurent,nou,potential;

        while(!q.empty()){
        nod=*q.begin();
        q.erase(*q.begin());

        curent=nod.ind;
        vizitat[curent]=true;
        costcurent=best[curent];

        for (i=0;i<vecin[curent].size();i++)
                  {
                      nou=vecin[curent][i];
                      if (vizitat[nou]) continue;

                      potential=costcurent + muchie[curent][i];
                      if (potential<best[nou])
                                   {
                                       q.erase(make_pair(best[nou],nou));
                                       best[nou]=costcurent + muchie[curent][i];
                                       q.insert(make_pair(best[nou],nou));
                                   }
                  }
        }
    }
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

    f>>n>>m;
    for(i=1;i<=n;i++)
          {
              f>>a>>b>>c;
              vecin[a].push_back(b);
              muchie[a].push_back(c);
          }

    best[1]=0;
    for (i=2;i<=n;i++)
        best[i]=inf,vizitat[i]=false;
    q.insert(make_pair(0,1));
    dijkstra();
    for(i=2;i<=n;i++)
            if(best[i]==inf) g<<"0"<<" ";
                             else g<<best[i]<<" ";

    return 0;
}