#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <limits.h>

#define INF INT_MAX
#define NMax 50005

using namespace std;

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

int N;
int Distanta[NMax];

vector < pair <int, int> > G[NMax];

struct Conditie
{
    bool operator() (int x, int y)
    {
        return Distanta[x] > Distanta[y];
    }
};

priority_queue <int, vector <int>, Conditie> Coada;

void Citire()
{
    int M, A, B, C;

    fin >> N >> M;
    for(int i = 1; i <= M; ++ i)
    {
        fin >> A >> B >> C;

        G[A].push_back( make_pair(B, C) );
    }
}

void Dijkstra(int nodStart)
{
    bool inCoada[NMax];

    for(int i = 1; i <= N; ++ i)
        Distanta[i] = INF;

    Distanta[nodStart] = 0;
    Coada.push(nodStart);
    inCoada[nodStart] = true;

    while( !Coada.empty() )
    {
        int nodCurent = Coada.top();
        Coada.pop();
        inCoada[nodCurent] = false;

        for(unsigned int i = 0; i < G[nodCurent].size(); ++ i)
        {
            int Vecin = G[nodCurent][i].first;
            int Cost = G[nodCurent][i].second;

            if(Distanta[Vecin] > Distanta[nodCurent] + Cost)
            {
                Distanta[Vecin] = Distanta[nodCurent] + Cost;
                if(inCoada[Vecin] == false)
                {
                    Coada.push(Vecin);
                    inCoada[Vecin] = true;
                }
            }
        }
    }
}

void Afisare()
{
    for(int i = 2; i <= N; ++ i)
    {
        if(Distanta[i] != INF)
            fout << Distanta[i] << ' ';

        else fout << 0 << ' ';
    }
}

int main()
{
    Citire();
    Dijkstra(1);
    Afisare();

    return 0;
}