#include <bits/stdc++.h>

using namespace std;
#define INF 0x3f3f3f3f
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
typedef long long ll;

using PI = pair<int,int>;
using VP = vector<PI>;
using VVP = vector<VP>;
using VI = vector<int>;

int n,m;
VVP G;
VI rez;

void Read();
void Dijkstra(int nod);
void Write();

int main()
{
    Read();
    Dijkstra(1);
    Write();
}

void Read()
{
    fin>>n>>m;
    int x,y,z;
    G = VVP(n+1);
    rez = VI(n+1,INF);
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        G[x].push_back({y,z});
    }
}

void Dijkstra(int nod)
{
    rez[nod] = 0;
    priority_queue<PI,VP,greater<PI>> pq;
    pq.push({0,nod});
    while(!pq.empty())
    {
        int dx = pq.top().first;
        int x = pq.top().second;
        pq.pop();
        if(dx>rez[x])
            continue;
        for(auto c:G[x])
        {
            int nodnou = c.first;
            int cost = c.second;
            if(rez[nodnou]>rez[x]+cost)
            {
                rez[nodnou] = rez[x]+cost;
                pq.push({rez[nodnou],nodnou});
            }
        }
    }
}

void Write()
{
    for(int i=2;i<=n;i++)
        if(rez[i]==INF)
        fout<<0<<" ";
        else
            fout<<rez[i]<<" ";
}