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

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);
    while (!q.empty()) {
        int nod = q.top();
        q.pop();
        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;
                    q.push(vecini[i].y);
                }
    }
    for (i = 2; i <= n; i++)
        if (dmin[i] == DMAX)
            fout << "0 ";
        else
            fout << dmin[i] << " ";
    fin.close();
    fout.close();
}