#include <fstream>
#include <vector>
#include <queue>
#define inf 1000000005

using namespace std;

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

const int Nmax = 50005;

int n, m, x, y, lungime;

int drum[Nmax], select[Nmax];
vector <pair <int, int>> A[Nmax];
queue <int> Q;

void dijkstra (int start)
{
    Q.push(start);

    while (!Q.empty())
    {
        int nod = Q.front();
        Q.pop();

        if (!select[nod])
        {
            select[nod] = 1;

            for (auto i = 0; i < A[nod].size(); i++)
            {
                int nod_urm = A[nod][i].first;
                int val_urm = A[nod][i].second;

                if (drum[nod_urm] > drum[nod] + val_urm)
                {
                    drum[nod_urm] = drum[nod] + val_urm;

                    if (!select[nod_urm])
                        Q.push(nod_urm);
                }
            }
        }
    }
}

int main()
{
    in >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        in >> x >> y >> lungime;
        A[x].push_back(make_pair(y, lungime));
    }

    for (int i = 2; i <= n; i++)
        drum[i] = inf;

    dijkstra(1);

    for (int i = 2; i <= n ; i++)
    {
        if (drum[i] == inf)
            out << 0 << ' ';
        else
            out << drum[i] << ' ';
    }

    return 0;
}