#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,a,b,m,c,d[105];
vector<pair<int,int>> adj[105];
void dks(int nod)
{
    for(int i=1; i<=n; i++) d[i]=INF;
    priority_queue<
    pair<int,int>,
         vector<pair<int,int>>,
         greater<pair<int,int>>
         >pq;
    d[nod]=0;
    pq.push({0,nod});
    while(!pq.empty())
    {
        int x=pq.top().second;
        int cost=pq.top().first;
        pq.pop();
        if(d[x]!=cost) continue;
        for(auto v: adj[x])
        {
            int ct=v.first;
            int vecin=v.second;
            if(d[vecin]>d[x]+ct)
            {
                d[vecin]=d[x]+ct;
                pq.push({d[vecin],vecin});
            }
        }
    }

}
int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        adj[a].push_back({c,b});
    }
    dks(1);
    for(int i=1; i<=n; i++)
    {
        if(d[i]!=INF)fout<<d[i];
        else fout<<0;
        fout<<' ';
    }
    return 0;
}