#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int N_max = 50005;
const int INF = 250000005;

vector < pair <int, int> > graph[N_max];

priority_queue < pair <int, int> > H;

int dmin[N_max];

bool viz[N_max];

int N, M;

void citire()
{
    int i, x, y, c;

    in >> N >> M;

    for(i = 1; i <= M; i++)
    {
        in >> x >> y >> c;

        graph[x].push_back(make_pair(y,c));
    }
}

void dijkstra(int node)
{
    int i, x, y, cost;

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

    // INSEREZ NODUL DE START

    dmin[node] = 0;
    H.push(make_pair(0, node));

    while(!H.empty())
    {
        while(!H.empty() && viz[ H.top().second ]) H.pop();

        if(H.empty()) break;

        x = H.top().second;
        H.pop();

        viz[x] = true;

        for(i = 0; i < graph[x].size(); i++)
        {
            y = graph[x][i].first;

            cost = graph[x][i].second;

            if(dmin[y] > dmin[x] + cost)
            {
                dmin[y] = dmin[x] + cost;

                H.push( make_pair( -dmin[y], y) );
            }
        }
    }
}

void write()
{
    for(int i = 2; i <= N; i++) out << dmin[i] << " ";
}

int main()
{
    citire();

    dijkstra(1);

    write();

    return 0;
}