#include<fstream>
#include<vector>

#define DIMN 50010
#define INF DIMN*1000

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector <pair<int,int> > L[DIMN];

int d[DIMN], v[DIMN], n, m, x, i, k, minim, vecin, cost,y,z;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        //pair<int,int> p;
        f>>x>>y>>z;
//        L[x].push_back(  p  );
        L[x].push_back(  make_pair(y,z)  );
    }

    d[1] = 0;
    for (i=2;i<=n;i++)
        d[i] = INF;

    while (1) {
        // calculam minim din d din dreptul val 1 din v
        minim = INF;
        for (i=1;i<=n;i++)
            if (v[i] == 0 && d[i] < minim) {
                minim = d[i];
                k = i;
            }

        if (minim == INF)
            break;
        v[k] = 1;

        for (i=0;i<L[k].size();i++) {
            vecin = L[k][i].first;
            cost = L[k][i].second;
            if (v[vecin] == 0 && d[vecin] > d[k] + cost)
                d[vecin] = d[k] + cost;
        }
    }
    for (i=2;i<=n;i++)
        if (d[i] != INF)
            g<<d[i]<<" ";
        else
            g<<"0 ";
    return 0;
}