#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define Nmax 50005
#define Infinit INT_MAX
using namespace std;

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

struct muchie
{
    int cost;
    int destinatie;
};

vector <muchie> graph[Nmax];
priority_queue < pair<int,int> > HEAP;
int dist[Nmax],viz[Nmax];

void Dijkstra()
{
    while(HEAP.empty() == 0)
    {
        pair <int,int> a = HEAP.top();
        HEAP.pop();
        int nod = a.second;
        int costI = -a.first;
        if(viz[nod] == 0)
        {
            viz[nod] = 1;
            dist[nod] = costI;
            int lim = graph[nod].size();
            for(int i = 0; i < lim; i++)
            {
                int vecin = graph[nod][i].destinatie;
            int cost = graph[nod][i].cost;
                if(cost + costI < dist[vecin])
                {
                    dist[vecin] = cost + costI;
                    HEAP.push( make_pair ((-1) * dist[vecin], vecin));
                }
            }
        }
    }
}

int main()
{
    int m, n, x, y, c;
    muchie A;
    f >> n >> m;
    for(int i = 0; i < m; i++)
    {
        f >> x >> y >> c;
        A.cost = c;
        A.destinatie = y;
        graph[x].push_back(A);

    }

    for(int i = 2; i <= Nmax; i++)
        dist[i]=Infinit;
    HEAP.push(make_pair(0,1));
    Dijkstra();
    for(int i = 2; i <= n; i++)
        if(dist[i] != Infinit)
            g << dist[i] << " ";
        else
            g << "0 ";

    return 0;
}