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

const int MAX =  (1 << 31) - 1;

vector<int> dijkstra(vector<vector<pair<int,int>>> &v,int nod = 1)
{
    priority_queue<pair<int,int>> q;
    vector<int> dist(v.size(),MAX);
    pair<int,int> p;
    p.first = 0;
    p.second = nod;
    q.push(p);
    dist[nod] = 0;
    while (q.size() != 0)
    {
        p = q.top();
        p.first = -p.first;
        q.pop();
        if (p.first != dist[p.second])
        {
            continue;
        }
        for (int i = 0; i < v[p.second].size(); i++)
        {
            pair<int,int> aux = v[p.second][i];
            if (dist[aux.first] > aux.second + p.first)
            {
                dist[aux.first] = aux.second + p.first;
                q.push({-dist[aux.first],aux.first});
            }
        }
    }
    return dist;
}

int main()
{
    int n,m;
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    in >> n >> m;
    vector<vector<pair<int,int>>>v (n+1);
    vector<int> res;
    for (int i = 0; i < m; i++)
    {
        int a,b,cost;
        in >> a >> b >> cost;
        pair <int,int> p;
        p.first = b;
        p.second = cost;
        v[a].push_back(p);
    }
    res = dijkstra(v,1);
    for (int i = 2; i < res.size(); i++)
    {
        if (res[i] == MAX)
        {
            out << "0 ";
        }
        else
        {
            out << res[i] << " ";
        }
    }
    in.close();
    out.close();
    return 0;

}