#include <fstream>
#include <vector>
#include <list>

using namespace std;

ifstream fi;
ofstream fo;

struct nod
{
    nod (int vd, int vv)
    {
        dest = vd;
        val = vv;
    };
    int dest;
    int val;
};

int m; int n;
vector<nod> graf[50001];
int grad[50001];
int sol[50001];
list<int> queue;

int main()
{
    fi.open("dijkstra.in");
    fi >> n >> m;
    // init
    for (int i=1; i<=n; i++)
        grad[i] = 0;
    for (int i=1; i<=n; i++)
        sol[i] = -1;
    sol[1] = 0;

    for (int i=1; i<=m; i++)
    {
        int a, b, c;
        fi >> a >> b >> c;
        graf[a].push_back(nod(b, c));
        grad[b]++;
    }
    fi.close();

    queue.push_back(1);

    while (!queue.empty())
    {
        int nod = queue.front();
        queue.pop_front();
        while (!graf[nod].empty())
        {
            int size = graf[nod].size() - 1;
            if (sol[graf[nod][size].dest] == -1)
                sol[graf[nod][size].dest] = sol[nod] + graf[nod][size].val;
            if (sol[graf[nod][size].dest] > (sol[nod] + graf[nod][size].val))
                sol[graf[nod][size].dest] = sol[nod] + graf[nod][size].val;
            grad[graf[nod][size].dest]--;
            if (grad[graf[nod][size].dest] == 0)
                queue.push_back(graf[nod][size].dest);
            graf[nod].pop_back();
        }
    }

    fo.open("dijkstra.out");
    for (int i=2; i <= n; i++)
        fo << sol[i] << " ";
    fo.close();
    return 0;
}