#include <fstream>
#include <vector>

#define INF 50001

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct arc
{
    int nod, cost;
};
vector<arc> vec[50001];
int n,d[50001],finaliz[50001],t[50001];

int main()
{
    int m,x;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>x;
        arc aux;
        fin>>aux.nod>>aux.cost;
        vec[x].push_back(aux);
    }
    for(int i=1; i<=n; i++)
        d[i]=INF; /// initial, toate nodurile au distanta minima a unui drum care incepe in 1 egala cu infinit
    d[1]=0; /// distanta de la 1 la 1 este 0
    finaliz[1]=1; /// si este distanta minima definitiva, deci finalizata
    for(int i=0; i<vec[1].size(); i++)
    {
        d[vec[1][i].nod]=vec[1][i].cost; /// pentru a nu avea in rest doar infinit la primul pas, trebuie sa marcam o distanta intermediara pentru toti vecinii lui 1
        t[vec[1][i].nod]=1;  /// toti acestia au fost imbunatatiti de 1
    }
    for(int pas=1; pas<n; pas++) /// mai avem n-1 noduri de imbunatatit (doar 1 este finalizat)
    {
        int Min=INF;
        int vf;
        for(int i=1; i<=n; i++)
        {
            if(!finaliz[i])
            {
                if(d[i]<Min)
                    {
                        Min=d[i];
                        vf=i;
                    }
            }
        }
        finaliz[vf]=1; /// la fiecare pas, alegem varful cu distanta minima dintre cele nefinalizate si acesta va deveni finalizat
        int l=vec[vf].size();
        for(int j=0; j<l; j++) /// actualizam toti vecinii celui pe care l-am finalizat
        {
            if(d[vec[vf][j].nod]>d[vf]+vec[vf][j].cost) /// daca al j-ulea vecin al lui vf este imbunatatit prin vf (j este doar un indice, nu un varf din graf)
            {
                d[vec[vf][j].nod]=d[vf]+vec[vf][j].cost;
                t[vec[vf][j].nod]=vf; /// al j-ulea vecin al lui vf a fost imbunatatit de vf;
            }
        }
    }
    for(int i=2; i<=n; i++)
        if(d[i]==INF)
            fout<<0<<" ";
        else fout<<d[i]<<" ";

    return 0;
}