#include<fstream>
#include<vector>
#define maxn 50005
#define lmax 2000000000

using namespace std;

vector< pair<int,int> > v[maxn];
int a[maxn], h[maxn], pos[maxn], n;

void up(int k){
    int x = h[k];
    while (k > 1 && a[h[k/2]] > a[h[k]]) {
        h[k] = h[k/2];
        pos[h[k]] = k;
        k = k/2;
    }
    h[k] = x;
    pos[x] = k;   
}

void down(int k){
    int son = 1, aux;
    while (son != 0){
        son = 0;
        if (k*2 <= n){
            son = k*2;
            if (k*2+1 <= n && a[h[k*2]] > a[h[k*2+1]])
                son = k*2+1;
            if (son != 0 && a[h[son]] > a[h[k]])
                son = 0;
        }
        if (son != 0){
            aux = h[son];
            h[son] = h[k];
            h[k] = aux;
            pos[h[k]] = k;
            pos[h[son]] = son;
            k = son;     
        }
    }    
}

int main(){
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int m, i, j, nodm, dist, poz, k1;
    pair<int, int> k;
    f>>n>>m;
    for (i = 1; i <= m; i++){
        f>>j>>k1>>dist;
        v[j].push_back(make_pair(k1, dist));
    }
    
    h[1] = 1;
    a[1] = 0;
    pos[1] = 1;
    for (i = 2; i <= n; i++){
        h[i] = i;
        a[i] = lmax;
        pos[i] = i;
    }
    int nr = n;
    while (n > 0){
        nodm = h[1];
        if (a[nodm] == lmax)
            break;
        h[1] = h[n];
        n--;
        down(1);
        for (i = 0; i < v[nodm].size(); i++){
            k = v[nodm][i];
            if (a[k.first] > a[nodm] + k.second){
                a[k.first] = a[nodm] + k.second;
                poz = pos[k.first];
                up(poz);
            }
        }               
    }    
    
    for (i = 2; i <= nr; i++)
        if (a[i] == lmax)
            g<<0<<" ";
        else 
            g<<a[i]<<" ";
    g<<'\n';
    
    return 0;
}