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

typedef pair<int, int> pi;

vector<pi> graph[50005];
priority_queue<pi, vector<pi>, greater<pi>> pq;
int d[50005], vis[50005];

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int n, m;
    f>>n>>m;
    int x, y, z;
    for(int i=0; i<m; i++)
    {
        f>>x>>y>>z;
        graph[x].push_back(make_pair(y,z));
    }
    for(int i=2; i<=n; i++)
        d[i] = 20001;
    pq.push(make_pair(0,1));
    int ok = 0;
    while(!pq.empty())
    {
        int k = pq.top().second;
        int val = pq.top().first;
        pq.pop();
        vis[k] = 1;
        ok = 1;
        if(d[k] < val )
            continue;
        for(auto edge : graph[k])
        {
            if(!vis[edge.first])
            {
                int newDist = d[k] + edge.second;
                if(newDist < d[edge.first])
                {
                    d[edge.first] = newDist;
                    pq.push(make_pair(newDist, edge.first));
                }
            }
        }
    }
    for(int i=2; i<=n; i++)
        g<<d[i]<<" ";
    return 0;
}