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

#define NMAX 50005
#define INF 1000000000

using namespace std;

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

struct Arc
{
    int vf, c;
};

int n, m; int start;
int x, y, c;
vector<Arc> g[NMAX];
int dmin[NMAX], pre[NMAX]; bool uz[NMAX];
int nr[NMAX];
int minim, vfmin;
int i, j;
bool negativ;

class ComparVf
{
public:
    bool operator() (const int& x, const int& y)
    {
        return dmin[x] > dmin[y];
    }
};
priority_queue<int, vector<int>, ComparVf> h;

int main()
{
    ///Citire
    fin >>n>>m; start = 1;
    for (i = 1; i <= m; ++i)
    {
        fin >>x>>y>>c;
        g[x].push_back({y, c});
    }

    ///Dijkstra
    uz[start] = 1;
    for (i = 0; i <= n; ++i) dmin[i] = INF;
    dmin[start] = 0;

    //parcurgem lista de adiacenta a lui start
    h.push(start);
    while (!h.empty())
    {
        vfmin = h.top(); h.pop();
        minim = dmin[vfmin];

        uz[vfmin] = 1;
        for (j = 0; j < g[vfmin].size(); ++j)
            if (dmin[g[vfmin][j].vf] > minim + g[vfmin][j].c)
            {
                dmin[g[vfmin][j].vf] = minim + g[vfmin][j].c;
                pre[g[vfmin][j].vf] = vfmin;
                h.push(g[vfmin][j].vf);
            }
    }

    for (i = 2; i <= n; ++i)
        if (dmin[i] == INF) fout <<0<<' ';
        else fout <<dmin[i]<<' ';
    fout <<'\n';
    fout.close();
    return 0;
}