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

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

int n, m, dist[lim], este[lim];
vector <pair<int, int> >v[lim];
int oo=(1<<30);
struct cmp
{
    bool operator() (int x, int y)
    {
        return dist[x]>dist[y];
    }
};

priority_queue <int, vector <int>, cmp> q;

void read()
{
    in>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        int x, y, cost;
        in>>x>>y>>cost;
        v[x].push_back(make_pair(y, cost));
    }
}

void dijkstra(int x)
{
    for(int i=1; i<=n; ++i)
        dist[i]=oo;
    dist[1]=0;
    q.push(x);
    while(!q.empty())
    {
        x=q.top();
        este[x]=0;
        for(int i=0; i<v[x].size(); ++i)
        {
            if(dist[v[x][i].first]>dist[x]+v[x][i].second)
            {
                dist[v[x][i].first]=dist[x]+v[x][i].second;
                if(este[v[x][i].first]==0)
                {
                    este[v[x][i].first]=1;
                    q.push(v[x][i].first);
                }
            }
        }
        q.pop();
    }
}

void afis()
{
    for(int i=1; i<=n; ++i)
    {
        if(dist[i]==oo)
            out<<"0 ";
        else
            out<<dist[i]<" ";
    }
}
int main()
{
    read();
    dijkstra(1);
    afis();
    return 0;
}