#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

//priority_queue<int> q;///in mod normal o coada cu prioritate iti da mereu cel mai mare element
///deci tu cand apelezi q.top() obtii in O(1) cel mai mare element din coada
/// poti sa inserezi sau sa stergi in O(log N)
const int NMAX = 50001;
int dist[NMAX];

struct comp
{
    bool operator()(int a, int b) /// trebuie sa definesc operatorul <
    {
        /// vreau ca functia sa returneze 1 atunci cand a < b
        /// in cazul meu a < b atunci d[a] > d[b]
        ///vreau ca cel cu distanta mai mica sa fie in varf
        return dist[a] > dist[b];
    }
};

priority_queue<int, vector<int>, comp> pq; ///imi da elementul cel mai mare
vector<pair<int, int>> adj[NMAX];///tin minte in ce nod pot merge si cu ce cost
bool inQ[NMAX];

void dijkstra(int sursa)
{
    dist[sursa] = 1;
    ///dist[i] = 0 -> nevizitat
    pq.push(sursa);
    while (!pq.empty())
    {
        int nodCrt = pq.top();
        pq.pop();
        inQ[nodCrt] = false;
        for (auto vec: adj[nodCrt])
        {
            int cost = dist[nodCrt] + vec.second;
            if (dist[vec.first] == 0 || cost < dist[vec.first])///daca nu a fost vizitat sau am gasit un cost mai mic
            {
                dist[vec.first] = cost;
                if (!inQ[vec.first])
                {
                    pq.push(vec.first);
                    inQ[vec.first] = true;
                }
            }
        }
    }
}

int main()
{
    int n, m;
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, cost;
        f >> u >> v >> cost;
        adj[u].emplace_back(v, cost);
    }
    dijkstra(1);
    for (int i = 2; i <= n; i++)
    {
        if (dist[i])
        {
            g << dist[i] - 1 << ' '; ///am initializat distantele cu 1
        }
        else
            g << 0 << ' ';
    }
    return 0;
}