#include <fstream>
#include <vector>
#define INF 50000000
#define DIM 50005
using namespace std;

struct drum {
    int nod;
    int len;
} heap[DIM];

int n,m,hDim,poz[DIM];
vector<drum> adj[DIM];

void decreaseKey(int key) {
    while(key>=1&&heap[key].len<heap[key/2].len) {
        swap(poz[heap[key].nod],poz[heap[key/2].nod]);
        swap(heap[key],heap[key/2]);
        key=key/2;
    }
}

void extractMin(int last) {
    swap(poz[heap[1].nod],poz[heap[last].nod]);
    swap(heap[1],heap[last]);
    int p=1;
    while(2*p<last&&heap[p].len>min(heap[2*p].len,heap[2*p+1].len)) {
        if(heap[2*p].len<heap[2*p+1].len||2*p+1>=last) {
            swap(poz[heap[p].nod],poz[heap[2*p].nod]);
            swap(heap[p],heap[2*p]);
            p=2*p;
        }
        else {
            swap(poz[heap[p].nod],poz[heap[2*p+1].nod]);
            swap(heap[p],heap[2*p+1]);
            p=2*p+1;
        }
    }
}

void dijkstra() {
    for(int i=1;i<=n;i++) {
        drum minim=heap[1];
        extractMin(n-i+1);
        for(int i=0;i<adj[minim.nod].size();i++) {
            if(minim.len+adj[minim.nod][i].len<heap[poz[adj[minim.nod][i].nod]].len) {
                heap[poz[adj[minim.nod][i].nod]].len=minim.len+adj[minim.nod][i].len;
                decreaseKey(poz[adj[minim.nod][i].nod]);
            }
        }
    }
}

int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;
    int a,b,c;
    for(int i=1;i<=m;i++) {
        fin>>a>>b>>c;
        adj[a].push_back({b,c});
    }
    for(int i=1;i<=n;i++) {
        heap[i]={i,INF};
        poz[i]=i;
    }
    heap[1].len=0;
    dijkstra();
    for(int i=2;i<=n;i++) {
        if(heap[poz[i]].len==INF)
            fout<<"0 ";
        else
            fout<<heap[poz[i]].len<<" ";
    }
    return 0;
}