#include <fstream>
#include <vector>
using namespace std;
const int MAX_SIZE = 50002, MAX_VALUE = 1999999999;

int h[MAX_SIZE]; /// heap
int poz[MAX_SIZE]; /// position in heap
int d[MAX_SIZE]; /// distance to the source
struct edge{
    int adj; /// adjacent node
    int cost;
};
vector < edge > v[MAX_SIZE];

void upHeap(int f){
    int key = h[f];
    while(f/2 && d[h[f/2]] > d[key]){
        h[f] = h[f/2];
        poz[h[f]] = f;
        f /= 2;
    }
    h[f] = key;
    poz[h[f]] = f;
}

void downHeap(int t, int l){
    int f = 0, key = h[t];
    while(f != t){
        f = t;
        if(f*2 <= l && d[key] > d[h[f*2]])
            t = f * 2;
        if(f*2+1 <= l && d[key] > d[h[f*2+1]])
            t = f * 2 + 1;
        h[f] = h[t];
        poz[h[f]] = f;
    }
    h[f] = key;
    poz[h[f]] = f;
}

void insertHeap(int val, int &l){
    h[++l] = val;
    poz[val] = l;
    upHeap(l);
}

int extractHeap(int &l){
    int rad = h[1];
    poz[rad] = 0;
    h[1] = h[l--];
    poz[h[1]] = 1;
    downHeap(1,l);
    return rad;
}

void initiate(int ns, int n, int &l){
    for(int i=1;i<=n;i++)
        d[i] = MAX_VALUE;
    d[ns] = 0;
    insertHeap(ns,l);
}

void dijkstra(int ns, int n){
    int l = 0, sz, rad, c, nbr;

    initiate(ns,n,l);

    while(l > 0){
        rad = extractHeap(l);
        sz = v[rad].size();

        for(int i=0;i<sz;i++){
            nbr = v[rad][i].adj;
            c = v[rad][i].cost;
            if(d[nbr] > d[rad] + c){
                d[nbr] = d[rad] + c;
                if(poz[nbr])
                    upHeap(poz[nbr]);
                else
                    insertHeap(nbr,l);
            }
        }
    }
}

void readData(int &n){
    int x, y, z, m;
    ifstream in("dijkstra.in");
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y>>z;
        v[x].push_back({y,z});
    }
    in.close();
}

void print(int n){
    ofstream out("dijkstra.out");
    for(int i=2;i<=n;i++)
        if(d[i] != MAX_VALUE)
            out<<d[i]<<" ";
        else
            out<<"0 ";
    out.close();
}

int main()
{
    int n;
    readData(n);
    dijkstra(1,n);
    print(n);
    return 0;
}