#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define inf 1073741823
#define nmx 50001
using namespace std;
///optimizam bellman-ford a.i. in loc de o coada obishnuita folosim o priority
///queue din care scoatem la fiecare pas nodul cu distantza minima (in fine, n-o
///sa fie mereu chiar nodul de dist. minima, dar se va mishca mult mai bine)
vector <pair<int,int> >lv[nmx];
int n,m,d[nmx];
struct comp{
        operator()(int x,int y)
            {return d[x]>d[y];}
    };
priority_queue <int,vector<int>,comp> q;
bool is_in_q[nmx];

int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;
    int i,x,y,cost,nodc;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        lv[x].push_back(make_pair(y,cost));
    }
    for(i=1;i<=n;i++)d[i]=inf;
    d[1]=0;q.push(1);is_in_q[1]=1;
    while(!q.empty())
    {
        nodc=q.top();q.pop();is_in_q[nodc]=0;
        ///facem o relaxare a distanțelor către nodurile cu care nodc e adiacent:
        for(auto&a:lv[nodc])
        {
            y=a.first;
            cost=a.second;
            if(d[nodc]+cost<d[y])
            {
                d[y]=d[nodc]+cost;
                if(!is_in_q[y])q.push(y);
            }
        }
    }
    for(i=2;i<=n;i++)
        if(d[i]==inf)fout<<0<<" ";
        else fout<<d[i]<<" ";
    return 0;
}