#include <iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<utility>
#include<functional>

using namespace std;

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

struct muchie{

    int distanta,  to;
};

vector<vector<muchie>> g;

void citire(int&n, int&m)
{
    fin >> n >> m;
    g.resize(n+1);
    for(int i = 0; i < m; ++i)
    {
        int x, y, dis;
        fin >> x >> y >> dis;
        g[x].push_back({dis, y});
    }
}

void dijk(int n)
{
    int siz_g = g.size();
    vector<int> d(siz_g+1, 20001);
    d[1] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
    q.push({0, 1});
    while(!q.empty())
    {
        int curent = q.top().second;
        int d_c = q.top().first;
        q.pop();
        if(d_c > d[curent]) continue;
            for(muchie mu : g[curent])
            {
                int x = mu.to;
                int dst = mu.distanta;
                if(d[x] > d[curent] + dst)
                {
                    d[x] = d[curent] + dst;
                    q.push({d[x], x});
                }
            }
    }
    for(int i = 2; i <= n; ++i)
    {
        fout << d[i] << ' ';
    }
}

int main()
{
    int n, m;
    citire(n, m);
    dijk(n);
    //fout << ":>><><><>";
    return 0;
}