#include <fstream>
#include <vector>
#include <set>

const int NMAX = 50005;
const int inf = 0x3f3f3f3f;

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

int N,M,a,b,c;
vector < pair<int, int> > v[NMAX];
long long D[NMAX];
set < pair<int,int> > S;

int main()
{
    f >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        f >> a >> b >> c;
        v[a].push_back(make_pair(b,c));
    }

    for (int i = 1; i <= N; ++i)
        D[i] = inf;

    D[1] = 0;
    S.insert(make_pair(0,1));
    while(!S.empty())
    {
        int nod = S.begin()->second;
        S.erase(S.begin());

        for (int i = 0; i < v[nod].size(); ++i)
        {
            int vecin = v[nod][i].first;
            int cost = v[nod][i].second;

            if (D[nod] + cost < D[vecin])
            {
                if (D[vecin] != inf)
                    S.erase(make_pair(D[vecin],vecin));
                D[vecin] = D[nod] + cost;
                S.insert(make_pair(D[vecin],vecin));
            }
        }
    }

    for (int i = 2; i <= N; ++i)
    {
        if (D[i] != inf)
            g << D[i] << " ";
        else g << "0 ";
    }

    f.close();
    g.close();

    return 0;
}