#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50004
#define INF 1000000006

using namespace std;

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


int n, m, p;

struct varf {
    int x;
    int cost;
};
vector <varf> G[NMAX];
bool uz[NMAX];
int cmin[NMAX];
int pre[NMAX];

class Compar {
    public:
    bool operator() (int a, int b) {
        return cmin[a] >= cmin[b];
    }
};
priority_queue <int, vector<int>, Compar> H;

void citire();
void dijkstra();
void afisare();

int main()
{
 citire();
 dijkstra();
 afisare();
 return 0;
}

void citire() {
    int x;
    varf vf;
    fin>>n>>m;
    for (int i=1; i<=m; i++) {
        fin>>x>>vf.x>>vf.cost;
        G[x].push_back(vf);
    }
    p=1;
}

void dijkstra() {
    varf vfmin;
    H.push(p);
    for (int i=1; i<=n; i++) cmin[i] = INF;
    cmin[p] = 0;
    for (int i=1; i<=n; i++) {
        vfmin.x = -1;
        while (!H.empty()) {
            vfmin.x = H.top();
            H.pop();
            if (!uz[vfmin.x]) break;
            vfmin.x = -1;
        }
        if (vfmin.x == -1) break;
        uz[vfmin.x] = 1;
        vfmin.cost = cmin[vfmin.x];
        for (int j=0; j<G[vfmin.x].size(); j++) {
            if (!uz[G[vfmin.x][j].x] && ((vfmin.cost + G[vfmin.x][j].cost) < cmin[G[vfmin.x][j].x])) {
                cmin[G[vfmin.x][j].x] = vfmin.cost + G[vfmin.x][j].cost;
                pre[G[vfmin.x][j].x] = vfmin.x;
                H.push(G[vfmin.x][j].x);
            }
        }
    }

}


void afisare() {
    for (int i=2; i<=n; i++)
        if (cmin[i] == INF) fout<<"0"<<' ';
            else fout<<cmin[i]<<' ';
    fout<<'\n';
}