#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e5;

const int INF = 0x3f3f3f3f;

vector <pair <int, int>> g[N + 1];

int n, m;

bool fre[N + 1];

int dist[N + 1];

struct compara
{
    bool operator()(int l, int c)
    {
        return dist[l] > dist[c];
    }
};

priority_queue <int, vector <int>, compara> pq;

int sursa;

void dijkstra(vector< pair <int, int>> g[N + 1], int start)
{
    for(int i = 1; i <= n; i++)
    {
        dist[i] = INF;
    }
    dist[start] = 0;
    pq.push(start);
    fre[start] = true;
    while(!pq.empty())
    {
        int curent = pq.top();
        pq.pop();
        fre[curent] = false;
        for(size_t i = 0; i < g[curent].size(); i++)
        {
            int vecin = g[curent][i].first;
            int cost = g[curent][i].second;
            if(dist[curent] + cost < dist[vecin])
            {
                dist[vecin] = dist[curent] + cost;
                if(fre[vecin] == false)
                {
                    pq.push(vecin);
                    fre[vecin] = true;
                }
            }
        }
    }
}

int main()
{
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int l, c, p;
        in >> l >> c >> p;
        g[l].push_back(make_pair(c, p));
        //g[c].push_back(make_pair(l ,p));
    }
    dijkstra(g, 1);
    for(int i = 2; i <= n; i++)
    {
        if(dist[i] != INF)
            out << dist[i] << " ";
        else
            out << "0 ";
    }
    return 0;
}