#include <bits/stdc++.h>
using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int INF = 1<<30, NMAX = 5e4;

struct EDGE
{
    int y,cost;
    bool operator <(const EDGE &aux) const{
        return cost > aux.cost;
    }
};

int n,m;
bool vis[NMAX + 5];
vector<EDGE> gr[NMAX + 5];
int ans[NMAX + 5];
priority_queue<EDGE, vector<EDGE>> pq;

int main()
{
    in>>n>>m;
    while(m--)
    {
        int x,y,c;

        in>>x>>y>>c;
        gr[x].push_back({y,c});
    }

    for(int i=1; i<=n; i++)
        ans[i]=INF;

    ans[1]=0;
    pq.push({1,0});
    while(!pq.empty())
    {
        EDGE fr=pq.top();

        if(!vis[fr.y])
        {
            for(auto it:gr[fr.y])
                if(ans[it.y] > ans[fr.y] + it.cost)
                {
                    ans[it.y]=ans[fr.y] + it.cost;
                    pq.push({it.y, ans[it.y]});
                }

            vis[fr.y]=1;
        }

        pq.pop();
    }

    for(int i=1; i<=n; i++)
    {
        if(ans[i] == INF) out<<0<<' ';
        else out<<ans[i]<<' ';
    }
    out<<'\n';

    return 0;
}