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

#define Nmax 50005
#define PAIR pair < int, int >

using namespace std;

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

vector < PAIR > Numbers[Nmax];

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

int Distanta[Nmax];
bool Visited[Nmax];

int vf, muchii, a, b, cost;

void Dijkstra(int x)
{
    int Vecin, Cost, Nod;

    Coada.push(x);
    Visited[x] = true;

    while(!Coada.empty())
    {
        Nod = Coada.top();

        Coada.pop();
        Visited[Nod] = false;

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

            if(Distanta[Nod] + Cost < Distanta[Vecin])
            {
                Distanta[Vecin] = Distanta[Nod] + Cost;
                if(!Visited[Vecin])
                {
                    Visited[Vecin] = true;
                    Coada.push(Vecin);
                }
            }
        }

    }
}

int main()
{
    fin >> vf >> muchii;
    for(int i = 1; i <= muchii; ++ i)
    {
        fin >> a >> b >> cost;
        Numbers[a].push_back({b, cost});
    }
    Distanta[1] = 0;
    for(int i = 2; i <= vf; ++ i)
        Distanta[i] = 1e9;

    Dijkstra(1);

    for(int i = 2; i <= vf; ++ i)
        if(Distanta[i] != 1e9)
            fout << Distanta[i] << " ";
        else
            fout << 0 << " ";
    return 0;
}