#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>

#define NMAX 50005
#define inf 0x3f3f3f

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct str
{
    int nod,cost;

    bool operator < (const str &a) const
    {
        return cost > a.cost;
    }
};

int n,m, D[NMAX];

vector<str> graf[NMAX];

priority_queue<str> Coada;

void initializare()
{
    f >> n >> m;
    for(int i=0; i<m; i++)
    {
        int nod1,nod2,cost;
        f >> nod1 >> nod2 >> cost;
        graf[nod1].push_back({nod2,cost});
    }

    memset(D, inf, sizeof D);
}

void Dijkstra(int nodStart)
{

    D[nodStart] = 0;
    Coada.push({nodStart,0});

    while(!Coada.empty())
    {
        int nodCurent = Coada.top().nod;
        int cost  = Coada.top().cost;
        Coada.pop();


        for(auto vecin:graf[nodCurent])
        {

            if(cost + vecin.cost  < D[vecin.nod])
            {
                D[vecin.nod] = cost + vecin.cost;
                Coada.push({vecin.nod, D[vecin.nod]});
            }

        }
    }
}

void afisare()
{
    for(int i=2; i<=n; i++)
    {
        if(D[i]!=inf) g << D[i] << ' ';
        else g << 0 << ' ';
    }
}


int main()
{
    initializare();
    Dijkstra(1);
    afisare();

    return 0;
}