#include<fstream>
#include<queue>
#define DMAX 1000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
queue <int> q;
struct graf{ int x, y, g; };
graf vecini[100000];
int dmin[100000];
bool inqueue[100000];
int n, m, a, b, c, i;

int main() {
    fin >> n >> m;
    for (i = 1; i <= m; i++){
        fin >> a >> b >> c;
        vecini[i].x = a; vecini[i].y = b; vecini[i].g = c;
    }
    for (i = 1; i <= n; i++)
        dmin[i] = DMAX;
    dmin[1] = 0;
    q.push(1);
    inqueue[1] = true;
    while (!q.empty()) {
        int nod = q.front();
        q.pop(); inqueue[nod] = false;
        for (i = 1; i <= m; i++)
            if (vecini[i].x == nod)
                if (dmin[vecini[i].y] > dmin[vecini[i].x] + vecini[i].g){
                    dmin[vecini[i].y] = dmin[vecini[i].x] + vecini[i].g;
                    if (!inqueue[vecini[i].y]){
                        q.push(vecini[i].y);
                        inqueue[vecini[i].y] = true;
                    }
                }
    }
    for (i = 2; i <= n; i++)
        fout << dmin[i] << " ";
}