#include <fstream>
#include <vector>
//#include "heap.h"
std::ifstream fin("dijkstra.in");
std::ofstream fout("dijkstra.out");
#define INF (1 << 30)
#define left(n) 2 * n
#define right(n) 2 * n + 1
template<class T>
class heap{
    private:
    std::vector<T> List;
    int totalSize = 0;
    public:
    heap(int n){
        List.resize(4 * n);
        totalSize = 4 * n;
    }
    int k = 0;
    void add(T value);

    T top(){
        return List[0];
    }

    void pop(){
        List[0] = List[k - 1];
        --k;
        heapify(0);
    }

    void heapify(int node);

    void print();
};
template<class T>
void heap<T>::add(T value){
    if(k >= totalSize)
        return ;
    List[k++] = value;
    int x = k - 1;
    while(List[x] < List[x / 2] && x != 0){
        std::swap(List[x], List[x / 2]);
        x /= 2;
    }
}

template<class T>
void heap<T>::heapify(int node)
{
    int i = node; T mn = List[node];
    if(mn > List[left(node)] && left(node) < k){
        mn = List[left(node)]; i = left(node);
    }
    else if(mn > List[right(node)] && right(node) < k){
        mn = List[right(node)]; i = right(node);
    }
    if(i != node){
        std::swap(List[node], List[i]);
        heapify(i);
    }
}

class int_pair{
    public:
    int first, second;
    int_pair() {}
    int_pair(int a, int b) : first(a), second(b) {}
    bool operator <(const int_pair& p1){
        if(first < p1.first)
            return true;
        if(first == p1.first)
            return second < p1.second;
        return false;
    }
    bool operator >(const int_pair& p1){
        if(first > p1.first)
            return true;
        return false;
    }
    friend std::ostream& operator <<(std::ostream& os, const int_pair &p1){
        os << p1.first << " ";
        return os;
    }
};
std::vector<int> dist;
std::vector<std::vector<int_pair>> V;
std::vector<int> viz;
int n, m;
void Dijkstra(int node){
    heap<int_pair> Heap(n);
    Heap.add(int_pair(0, node));
    dist[node] = 0;
    while(Heap.k != 0){
        int node = Heap.top().second;
        Heap.pop();
        if(viz[node])
            continue;
        viz[node] = 1;
        for(int_pair it : V[node]){
            if(dist[it.first] > dist[node] + it.second){
                dist[it.first] = dist[node] + it.second;
                Heap.add(int_pair(dist[it.first], it.first));
            }
        }
    }
}
int main(){
    fin >> n >> m;
    int x, y, c;
    viz = std::vector<int> (n + 1);
    dist = std::vector<int> (n + 1, INF);
    V = std::vector<std::vector<int_pair>> (n + 1);
    for(int i = 1; i <= m; i++){
        fin >> x >> y >> c;
        V[x].push_back(int_pair(y, c));
    }
    Dijkstra(1);
    for(int i = 2; i <= n; i++){
        fout << dist[i] << " ";
    }
}