#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
//ifstream fin("date.in");
//ofstream fout("date.out");

int n,m;
int D[250000];
priority_queue< pair<int, int> , vector< pair<int, int> >, greater< pair<int, int> > > Q;
vector < vector < pair <int, int> > > G(250000);

void dijkstra(int s){
    for(int i=1;i<=n;i++)
        D[i] = 250000;
    Q.push({0, s});
    while(!Q.empty()){
        int dist = Q.top().first;
        s = Q.top().second;
        Q.pop();
        if(dist > D[s])
            continue;
        for(auto x:G[s])
            if(D[x.first] > dist + x.second)
            {
                D[x.first] = dist + x.second;
                Q.push({D[x.first], x.first});
            }
    }
    for(int i=2;i<=n;i++)
        if(D[i]==250000)
            fout<<"0 ";
        else
            fout<<D[i]<<" ";
}

int main(int argc, char* argv[])
{
    fin>>n>>m;
    int x, y, c;
    for(int i=0;i<m;i++)
    {
        fin>>x>>y>>c;
        G[x].push_back({y, c});
    }
    dijkstra(1);
    fin.close();
    fout.close();
    return 0;
}