#include <cstdio>
#include <fstream>
#include <vector>

using namespace std;

#define N 50005
#define inf 1<<30

struct nod {
int varf;
int cost;
};

vector<nod> v[N];
int n,m;

void dijkstra (int start){

    vector<int> a(n+1);
    vector<int> c(n+1,inf);
    int p;
    for(vector<nod>::iterator it=v[start].begin();it<v[start].end();++it)
        c[(*it).varf]=(*it).cost;
    c[start]=0;
    a[start]=1;
    for(int k=1;k<n;++k){
        p=0;
        for(int i=1;i<=n;++i)
            if(a[i]==0 && c[i]<c[p])
                p=i;
        if(!p)
            k=n;
        else{
            a[p]=1;
            for(vector<nod>::iterator it=v[p].begin();it<v[p].end();++it)
                if(a[(*it).varf]==0)
                    if(c[(*it).varf]>c[p]+(*it).cost)
                        c[(*it).varf]=c[p]+(*it).cost;
        }
    }

    for(int i=2;i<=n;++i)
    printf("%d ",c[i]==inf ? 0 : c[i]);

}

int main ()
{

    ifstream in ("dijkstra.in");
    freopen ("dijkstra.out","w",stdout);
    in>>n>>m;
    for(;m;--m){
        nod x;
        int i;
        in>>i>>x.varf>>x.cost;
        v[i].push_back(x);
    }
    dijkstra (1);
    printf("\n");

return 0;}