#include <bits/stdc++.h>

using namespace std;

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

priority_queue< pair<int,int>,vector< pair<int,int> >, greater< pair<int,int>>> q;

int n,m,dist[50005];

const int inf = 100000000;

vector <pair <int,int>> V[250005];

int main()
{
    fin>>n>>m;
    for(int i = 1;i<=m;i++)
    {
        int a,b,d;
        fin>>a>>b>>d;
        V[a].push_back(make_pair(b,d));
    }

    dist[1] = 0;
    q.push(make_pair(0,1));
    for(int i = 2;i<=n;i++)
    {
        dist[i] = inf;
    }
    while(!q.empty())
    {
        pair<int,int> varf;
        varf = q.top();
        q.pop();
        if(varf.first>dist[varf.second])
            continue;
        for(auto it:V[varf.second])
        {
            if(dist[it.first]>it.second + varf.first)
            {
                dist[it.first] = it.second + varf.first;
                q.push(make_pair(dist[it.first],it.first));
            }
        }
    }
    for(int i = 2;i<=n;i++)
    {
        if(dist[i]==inf)
            dist[i] = 0;
        fout<<dist[i]<<' ';
    }
}