#include <bits/stdc++.h>

#define Nmax 50005
#define oo (1 << 25)

using namespace std;

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

int N, M;
int Distances[Nmax];
bool Seen[Nmax];

vector < pair < int, int > > Graph[Nmax];

struct compareDistances
{
    bool operator () (int first, int second)
    {
        return Distances[first] > Distances[second];
    }
};

priority_queue < int, vector < int >, compareDistances > Q;

int main()
{
    fin >> N >> M;
    for(int i = 1; i <= M; ++i)
    {
        int home, destination, cost;
        fin >> home >> destination >> cost;
        Graph[home].push_back({destination, cost});
    }
    for(int i = 1; i <= N; ++i)
        Distances[i] = oo;
    Seen[1] = 1;
    Q.push(1);
    Distances[1] = 0;
    while(Q.empty() == 0)
    {
        int currenNode = Q.top();
        Q.pop();
        for(int i = 0; i < Graph[currenNode].size(); ++i)
        {
            int neighbour = Graph[currenNode][i].first;
            int cost = Graph[currenNode][i].second;
            if(Distances[currenNode] + cost < Distances[neighbour])
            {
                Distances[neighbour] = cost + Distances[currenNode];
                if(Seen[neighbour] == false)
                {
                    Seen[neighbour] = true;
                    Q.push(neighbour);
                }
            }
        }
    }
    for(int i = 2; i <= N; ++i)
        if(Distances[i] == oo)
            fout << "0 ";
        else
            fout << Distances[i] << " ";
    return 0;
}