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

using namespace std;

#define inf 2e9

vector<pair<int,int>> v[300001];
set<pair<int,int>> s;

int dmin[300001];

void dijk()
{
    while(!s.empty())
    {
        int x = s.begin()->second;
        int cx = s.begin()->first;
        s.erase(s.begin());

        for(int i = 0; i < v[x].size(); i++)
        {
            int y = v[x][i].first;
            int cy = v[x][i].second;

            if(dmin[y] > dmin[x] + cy)
            {
                if(dmin[y] != inf)
                    s.erase(s.find(make_pair(dmin[y], y)));

                dmin[y] = dmin[x] + cy;
                s.insert(make_pair(dmin[y], y));
            }
        }
    }
}

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

    int n, m;
    f >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        dmin[i] = inf;
        int x, y, d;
        f >> x >> y >> d;
        v[x].push_back(make_pair(y,d));
    }
    dmin[1] = 0;
    s.insert(make_pair(0,1));

    dijk();

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

    return 0;
}