#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int nmax= 50000;
const int mmax= 250000;
const int inf= 1<<30;

bool u[nmax+1];

int n, m;
int d[nmax+1];

struct str {
    int x, y;
};

struct str_cmp {
    bool operator () (const str &x, const str &y) {
        return x.y>y.y;
    }
};

priority_queue <str, vector <str>, str_cmp> h;
vector <str> g[nmax+1];

inline str mp( int x, int y ) {
    str sol;
    sol.x= x, sol.y= y;

    return sol;
}

void dijkstra( int x ) {
    for ( int i= 1; i<=n; ++i ) {
        d[i]= inf;
    }
    d[x]= 0;

    for ( h.push(mp(x, 0)); !h.empty(); ) {
        str x= h.top();
        h.pop();

        for ( vector <str>::iterator it= g[x.x].begin(); it!=g[x.x].end(); ++it ) {
            if ( d[x.x]+(*it).y<d[(*it).x] ) {
                d[(*it).x]= d[x.x]+(*it).y;

                if ( u[(*it).x]==0 ) {
                    u[(*it).x]= 1;
                    h.push(mp((*it).x, d[(*it).x]));
                }
            }
        }
    }
}

int main(  ) {
    fin>>n>>m;
    for ( int i= 1, x, y, z; i<=m; ++i ) {
        fin>>x>>y>>z;

        g[x].push_back(mp(y, z));
    }

    dijkstra(1);

    for ( int i= 2; i<=n; ++i ) {
        if ( d[i]==inf ) {
            d[i]= 0;
        }

        fout<<d[i]<<" ";
    }
    fout<<"\n";

    return 0;
}