#include <fstream>
#include <cstring>
#include <vector>
#include <set>
#include <utility>
#define ff first
#define ss second
#define mp make_pair

#define BIG 0x7fffffff

using namespace std;

vector<pair <int,int> > grf[50001];
int obg[16],n;

vector <int> dijkstra(int start) {
    vector <int> v(n+1, BIG);
    pair<int,int> p,x;
    v[start] = 0;
    set< pair<int,int> > frontier;
    p.ff = 0; p.ss = start;
    frontier.insert(p);
    while (!frontier.empty()) {
        p = *frontier.begin();
        frontier.erase(frontier.begin());
        for (int i=0; i<grf[p.ss].size(); i++) {
            if (p.ff + grf[p.ss][i].ff < v[grf[p.ss][i].ss] ) {
                v[grf[p.ss][i].ss] = p.ff + grf[p.ss][i].ff;
                x.ff = v[grf[p.ss][i].ss];
                x.ss = grf[p.ss][i].ss;
                frontier.insert(x);
            }
        }
    }
    return v;
}

int main() {
    int m,k,i,j,a,b,d,l;
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    in>>n>>m;
    //in>>k;
    /*for (i=1; i<=k; i++)
        in>>obg[k];*/

    for (i=1; i<=m; i++) {
        in>>a>>b>>d;
        grf[a].push_back( mp (d,b));
        //grf[b].push_back( mp (d,a));
    }

    vector <int> dist = dijkstra(1);
    for (i=2; i<dist.size(); i++)
        if (dist[i]== BIG)
            out<<0<<' ';
        else
            out<<dist[i]<<' ';
    out<<'\n';
    out.close();
    return 0;
}