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

using namespace std;

vector< pair<int, int> > v[50005];
set< pair<int, int> > s;
int n, m, d[50005];

int main()
{
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");
    fin >> n >> m;
    while(m--){
        int x, y, z;
        fin >> x >> y >> z;
        v[x].push_back(make_pair(y, z));
    }
    for (int i = 0; i < 50005; ++i)
        d[i] = 2000000000;
    s.insert(make_pair(0, 1));
    d[1] = 0;
    while(!s.empty()){
        int k = s.begin()->second;
        s.erase(s.begin());
        for (unsigned i = 0; i < v[k].size(); ++i)
            if(d[v[k][i].first] > d[k] + v[k][i].second){
                if(d[v[k][i].first] != 2000000000)
                    s.erase(s.find(make_pair(d[v[k][i].first], v[k][i].first)));
                d[v[k][i].first] = d[k]  + v[k][i].second;
                s.insert(make_pair(d[v[k][i].first], v[k][i].first));
            }
    }
    for (int i = 2; i <= n; ++i)
        if(d[i] == 2000000000)
            fout << "0 ";
        else
            fout << d[i] << " ";
    fin.close();
    fout.close();
    return 0;
}