#include <fstream>
#include <vector>
#include <queue>

#define INF 2000000001
#define NMAX 50010
#define fi first
#define se second

using namespace std;

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

priority_queue < pair <int, int> > p;
vector <pair <int, int> > v[NMAX];
pair<int, int> crt;
int n, m, i, j, d[NMAX], x, y, c;

void dijkstra(int x);

int main()
{
    fin >> n >> m;
    for(i = 1; i <= m; ++i)
    {
        fin >> x >> y >> c;
        crt.fi = c;
        crt.se = y;
        v[x].push_back(crt);
    }
    dijkstra(1);
    for(i = 2; i <= n; ++i)
        if(d[i] != INF)
            fout << d[i] << ' ';
        else
            fout << "0\n";
    return 0;
}


void dijkstra(int x)
{
    int i;
    for(i = 1; i <= n; ++i)
        d[i] = INF;
    d[x] = 0;

    p.push(make_pair(0, x));

    while(!p.empty())
    {
        pair<int, int > pi = p.top();
        p.pop();

        int nod=pi.se;
        // d[nod] == pi.first
        int dnod=-pi.fi;

        for(i = 0;i < v[nod].size(); ++i)
        {
            if(d[v[nod][i].se] > dnod + v[nod][i].fi)
            {
                d[v[nod][i].se] = dnod + v[nod][i].fi;
                p.push(make_pair(-d[v[nod][i].se], v[nod][i].se));
            }

        }
    }
}