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

using namespace std;

int n, m;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
vector<pair<int, int> > adj[4001];
vector<int> s;

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

void dijkstra()
{
    pq.push({1, 0});
    s[1] = 0;
    while(!pq.empty())
    {
        pair<int, int> p = pq.top();
        pq.pop();
        for(int i = 0; i < adj[p.first].size(); i++)
            if(s[adj[p.first][i].first] > p.second + adj[p.first][i].second)
            {
                s[adj[p.first][i].first] = p.second + adj[p.first][i].second;
                pq.push({adj[p.first][i].first, adj[p.first][i].second});
            }
    }
}

int main()
{
    f>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        f>>a>>b>>c;
        adj[a].push_back({b, c});
    }
    for(int i = 0; i <= n; i++)
        s.push_back(1000);

    dijkstra();

    for(int i = 2; i <= n; i++)
        g<<s[i]<<" ";
    return 0;
}