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

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

int n, m;
long long d[50001];
int viz[50001];

vector< pair <int, int> > a[50001];

struct comp
{
    bool operator() (int x, int y)
    {
        return d[x] < d[y];
    }
};
priority_queue <int, vector <int>, comp> q;

void citire()
{
    fin >> n >> m;

    int x, y, c;
    for(int i = 0; i < m; ++i)
    {
        fin >> x >> y >> c;
        a[x].push_back(make_pair(y, c));
    }
}

void dijkstra(int start)
{
    for(int i = 1; i <= n; ++i)
        d[i] = INF;

    d[start] = 0;
    viz[start] = 1;
    q.push(start);
    while(!q.empty())
    {
        int el = q.top();
        q.pop();
        viz[el] = 0;

        int l = a[el].size();
        for(int i = 0; i < l; ++i)
        {
            int v = a[el][i].first;
            int c = a[el][i].second;
            if(d[v] > d[el] + c)
                d[v] = d[el] + c;
            if(!viz[v])
            {
                q.push(v);
                viz[v] = 1;
            }
        }
    }
}

void afisare()
{
    for(int i = 2; i <= n; ++i)
        if(d[i] == INF)
            fout << 0 << ' ';
        else
            fout << d[i] << ' ';
}

int main()
{
    citire();
    dijkstra(1);
    afisare();
    return 0;
}