#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
typedef pair<int,int> pa ;
const int N = 500001, Inf =1e9;
int n ,m ;
int cost[N],viz[N], can[N];
struct cond
{
    bool operator()(int x, int y)
    {
        return cost[x] > cost[y];
    }
};
priority_queue<int, vector<int>, cond > q;
int x , y ,z ;
vector <pair<int,int> > L[N];
void read();
void init();
void dijkstra();
//void push(int x)
//{
//    for(auto i : L[x])
//    {
//
//    }
//}
void write();
int main() {

    read();
    init();
    dijkstra();
    write();
    return 0;
}
void read()
{
    fin >> n >> m;
    for(int i =1 ;i <=m ;i ++)
    {
        fin >> x >> y >> z;
        L[x].push_back({y,z});
    }
}
void init()
{
    for(int i = 1 ;i <=n; i ++)
        cost[i] = Inf;
    cost[1] = 0;
    viz[1] = 1;
    q.push(1);
}
void dijkstra()
{
    while(!q.empty())
    {
        int curr = q.top();
        q.pop();
        viz[curr] = 0;
        for(pa i : L[curr])
        {
            if(cost[curr] + i.second <cost[i.first])
            {
                cost[i.first] = cost[curr] + i.second;
                if(!viz[i.first])
                {
                    q.push(i.first);
                    viz[i.first] = 1;
                }
            }
        }
    }
}
//void dijkstra()
//{
//    while (s.empty())
//    {
//        auto nod = s.begin();
//        while (true) {
//            nod = s.begin();
//            if (viz[nod->second.second.first])
//                s.erase(nod);
//            else {
//                break;
//                }
//            }
//        int cost_curr =nod ->first;
//        int cost_lat = nod->second.first;
//        auto puncte = nod->second.second;
//            viz[puncte.first] = 1;
//            push(puncte.second);
//    }
//}
void write()
{
    for(int i =2 ;i <=n; i ++)
        if(cost[i] == Inf)
            fout << 0 << " ";
        else
        fout << cost[i]<<" ";
}