#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
ofstream fout("dijkstra.out");
ifstream fin("dijkstra.in");

/*struct asdf{
    int a;
    int b;

    bool operator< (const asdf a) const{
        return b > a.b;
    }
};*/

struct asdfg{
    int fs;
    int sc;
};

//vector <asdf> q;
set <pair <int, int> > q;
int viz[50010];
vector <asdfg> v[50010];
int n,m,x,y,c;

void dijkstra(int nod){
    //q.push_back({nod, *viz[nod]});
    q.insert({0, 1});
    viz[nod] = -1;

    while(q.size() > 0){
        nod = q.begin() -> second;
        q.erase(q.begin());
        for(int i = 0; i < v[nod].size(); i++){
            if(viz[v[nod][i].fs] == 0){
                viz[v[nod][i].fs] = (viz[nod] == -1 ? 0 : viz[nod]) + v[nod][i].sc;
                //q.push_back({v[nod][i].fs, *viz[v[nod][i].fs]});
               // push_heap(q.begin(), q.end());
               q.insert({viz[v[nod][i].fs], v[nod][i].fs});
            }

            else if(viz[v[nod][i].fs] > (viz[nod] == -1 ? 0 : viz[nod]) + v[nod][i].sc){
                q.erase(q.find({viz[v[nod][i].fs], v[nod][i].fs}));
                viz[v[nod][i].fs] = (viz[nod] == -1 ? 0 : viz[nod]) + v[nod][i].sc;
                q.insert({viz[v[nod][i].fs], v[nod][i].fs});
            }
        }
    }
}

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

    for(int i = 1; i <= m; i++){
        fin >> x >> y >> c;

        v[x].push_back({y, c});
        //v[y].push_back({x, c});
    }

    dijkstra(1);

    for(int i = 2; i <= n; i++){
        fout << viz[i] << ' ';
    }

    return 0;
}