#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50002
#define INF 1000000002
using namespace std;

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

int n, p = 1;
vector<pair<int, int> > G[NMAX]; //varf si cost
int cmin[NMAX];
bool uz[NMAX];
class ComparVf
{
public:
    bool operator() (int x, int y)
    {
        return cmin[x] > cmin[y];
    }
};
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > H;

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

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

void citire()
{
    int i, j, c, m;
    pair<int, int> vf;
    fin >> n >> m;
    for(int k = 0; k < m; k++)
    {
        fin >> i >> j >> c;
        //am arc de la i la j de cost c
        //in lista de adiacenta a lui i trebuie sa punem varful j si costul j
        vf.first = j;
        vf.second = c;
        G[i].push_back(vf);
    }
}

void dijkstra()
{
    int i, x, vfmin, minim;
    pair<int, int> pp;
    //initializare
    pp.first = 0;
    pp.second = p;
    H.push(pp);
    for(i = 1; i <= n; i++)
        cmin[i] = INF;
    cmin[p] = 0;

    while(!H.empty())
    {
        vfmin = H.top().second;
        H.pop();
        if(cmin[vfmin] == INF) break;
        //vfmin este selectat
        //optimizez costurile catre celelalte varfuri, trecand prin vfmin
        //parcurg lista de adiacenta a lui vfmin
        if(!uz[vfmin]){
            int idk = G[vfmin].size();
            for(i = 0; i < idk; i++){
                x = G[vfmin][i].first;
                int c = G[vfmin][i].second;
                if(cmin[x] > cmin[vfmin] + c){
                    cmin[x] = cmin[vfmin] + c;
                    pp.first = cmin[x];
                    pp.second = x;
                    H.push(pp);
                }
            }
        }

        uz[vfmin] = 1;
    }
}

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