#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

ofstream fo("dijkstra.out");
ifstream fi("dijkstra.in");

struct nod
{
    int val,cost;
};
priority_queue <nod> coada;

bool operator <(nod a,nod b)
{
    if(a.cost<b.cost)
        return false;
    return true;
}

int Dmin[50006];
vector <nod> vecini[50006];
int n,m,a,b,C;
int main()
{

 fi>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fi>>a>>b>>C;
        nod x;
        x.cost=C;
        x.val=b;
        vecini[a].push_back(x);
        Dmin[i]=2000000000;
    }


    nod start;
    start.val=1;
    start.cost=0;
    Dmin[1]=0;

    coada.push(start);

    while(coada.empty()==false)
    {
        int Curent=coada.top().val;
        int Valoare=coada.top().cost;
        coada.pop();

      if(Dmin[Curent]!=Valoare)
       continue;

        for(nod vecin:vecini[Curent])
        {
            int NodVecin=vecin.val;
            int CostVecin=vecin.cost;

            if(Dmin[NodVecin]>Valoare+CostVecin)
            {
                nod aux=vecin;
                aux.cost+=Valoare;
                Dmin[NodVecin]=aux.cost;
                coada.push(aux);
            }
        }

    }

    for(int i=2; i<=n; i++)
        {
          if(Dmin[i]==2000000000)
          fo<<0<<" ";
          else
          fo<<Dmin[i]<<" ";
        }

    fi.close();
    fo.close();
    return 0;
}