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

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

bool operator <(arc a1,arc a2)
{

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

    return false;
}

int n,m,x1,x2,L;
int 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())
    {
        while(!coada.empty() && viz[coada.top().a])coada.pop();
        if(!coada.empty())
        {
            arc curent=coada.top();
            coada.pop();
            viz[curent.a]=1;

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

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


    }


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

    return 0;
}