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

ofstream fo("dijkstra.out");
ifstream fi("dijkstra.in");
struct arc
{
    long long a,lungime;
};

bool operator <(arc a1,arc a2)
{

    if(a1.lungime>a2.lungime)
        return true;

    return false;
}

long long n,m,x1,x2,L;
long long drum[50005];
bool viz[50005];
vector<arc> vecini[50005];
priority_queue<arc> coada;
arc citit;


int main()
{

    fi>>n>>m;

    for(int i=1; i<=m; i++)
    {
        fi>>x1>>x2>>L;
        citit.a=x2;
        citit.lungime=L;
        vecini[x1].push_back(citit);

    }
    for(int i=1;i<=n;++i)drum[i]= 2000000000;


    arc pornire;
    pornire.a=1;
    drum[1]=0;
    pornire.lungime=0;
    coada.push(pornire);


    while(!coada.empty())
    {
        arc curent=coada.top();
        coada.pop();


        for(auto vecin:vecini[curent.a] )/// merg pe vecini
        {
            if(drum[vecin.a]>drum[curent.a]+vecin.lungime)
            {

                drum[vecin.a]=drum[curent.a]+vecin.lungime;
                coada.push(vecin);
            }
        }


    }


    for(int i=2; i<=n; i++)
        fo<<drum[i]<<" ";

    return 0;
}