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

using namespace std;

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

struct Node{
    int dist, next;
    bool operator < (const Node & other) const{
        return dist > other.dist;
    }
};

vector<vector<pair<int, int>>> graf;
vector<int> distant;

void dijkstra(int start, int n)
{
    distant.assign(n+1, 20009);
    priority_queue <Node>pq;
    distant[start] = 0;
    pq.push({0, start});
    while(!pq.empty())
    {
        Node curent = pq.top();
        pq.pop();
        int u = curent.next;
        int d = curent.dist;
        
        if(d > distant[u]) continue;
        
        for(auto vefin : graf[u])
        {
            int v = vefin.first;
            int cost = vefin.second;
            
            if(distant[u] + cost < distant[v])
            {
                distant[v] = distant[u] + cost;
                pq.push({distant[v], v});
            }
        }
    }
}

int main()
{
    int muchii, noduri, a, b, c;
    fin >> noduri >> muchii;
    graf.resize(noduri+1);
    for(int i = 0; i < muchii; i++)
    {
        fin >> a >> b >> c;
        graf[a].push_back({b, c});
    }
    dijkstra(1, noduri);
    for(int i = 2; i <= noduri; i++)
    {
        if(distant[i] == 20009)
            fout << '0' << ' ';
        else
            fout << distant[i] << ' ';
    }
    
    return 0;
}