#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define N_MAX 50010
#define M_MAX 250010
#define INF 987654321

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int n, m, c[N_MAX];
vector < pair <int, int> > v[N_MAX];
bool visited[N_MAX];

void read()
{
    in >> n >> m;
    for(int i = 0, a, b, c; i < m; i++)
    {
        in >> a >> b >> c;
        v[a].push_back(make_pair(b,c));
    }
}

void Dijkstra()
{

    for(int i = 2; i <=n; i++)
        c[i] = INF;
    priority_queue < pair <int, int>, vector < pair <int, int> >, greater < pair <int, int> > > q;
    q.push(make_pair(1, 0));
    while(!q.empty())
    {
        node = q.top().first;
        q.pop();
        //visited[node] = true;
        for(int i = 0; i < v[node].size(); i++)
        {
            if(c[v[node][i].first] > c[node] + v[node][i].second)
            {
                c[v[node][i].first] = c[node] + v[node][i].second;
                q.push(make_pair(v[node][i].first, c[v[node][i].first]));
            }
        }
    }
}

void print()
{
    for(int i = 2; i <= n; i++)
        if(c[i] != INF) out << c[i] << " ";
        else out << 0 << " ";
}

int main()
{
    read();
    Dijkstra();
    print();
    return 0;
}