#include<fstream>
#include<vector>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
    int noduri;
    int muchii;
    vector<int> adiacenta[100001];
    void BF()
    {
        vector <int> costuri[10001], distanta, v;
        in >> noduri >> muchii;
        distanta.resize(noduri + 1);
        v.resize(noduri + 1);
        /*for (int i = 0; i <= muchii; i++)
        {
            v.push_back(0);
            adiacenta[i].resize(noduri + 1);
            costuri[i].resize(noduri + 1);
        }*/
        int x, y, z;
        for (int i = 1; i <= muchii; i++)
        {
            in >> x >> y >> z;
            adiacenta[x].push_back(y);
            costuri[x].push_back(z);
        }
        int final = 0, inceput = 0;
        for (int i = 1; i <= noduri; i++)
            distanta[i] = 100001;
        v[inceput] = 1;
        v[final] = 1;
        distanta[1] = 0;
        while (inceput <= final)
        {
            x = v[inceput];
            inceput++;
            for (int i = 0; i < adiacenta[x].size(); i++)
                if (distanta[adiacenta[x][i]] > distanta[x] + costuri[x][i])
                {
                    distanta[adiacenta[x][i]] = distanta[x] + costuri[x][i];
                    v[++final] = adiacenta[x][i];
                }
        }
        for (int i = 2; i <= noduri; i++)
            if (distanta[i] == 100001)
                out << 0;
            else
                out << distanta[i] << " ";

    }
int main()
{
	BF();
	return 0;
}