#include<fstream>
#include<queue>
#include<algorithm>
#define DMAX 1000000
#include<vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector < pair<int, int> > v[50010];
int dmin[100000];
int n, m, a, b, c, i;
struct cmp
{
    bool operator() (int x,int y)
    {
        return dmin[x] > dmin[y];
    }
};
priority_queue <int,vector <int>,cmp> q;

int main() {
    fin >> n >> m;
    for (i = 1; i <= m; i++){
        fin >> a >> b >> c;
        v[a].push_back(make_pair(b,c));
    }
    for (i = 1; i <= n; i++)
        dmin[i] = DMAX;
    dmin[1] = 0;
    q.push(1);
    while (!q.empty()) {
        int nod = q.top();
        q.pop();
          for(i = 0; i < v[nod].size(); i++)
            if (dmin[v[nod][i].first] > dmin[nod] + v[nod][i].second){
                dmin[v[nod][i].first] = dmin[nod] + v[nod][i].second;
                q.push(v[nod][i].first);
            }
    }
    for (i = 2; i <= n; i++)
        if (dmin[i] == DMAX)
            fout << "0 ";
        else
            fout << dmin[i] << " ";
    fin.close();
    fout.close();
}