#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50005
#define INF 1000000000
using namespace std;
ifstream si("dijkstra.in");
ofstream so("dijkstra.out");
struct edge
{
    int p,c;
    bool operator <(const edge &var) const
    {
        return c>var.c;
    }
};
vector<edge> v[NMAX];
int d[NMAX];
priority_queue<edge> x;
int main()
{
    int n,m;
    si>>n>>m;
    int a,b,c;
    for(int i=0;i<m;++i)
    {
        si>>a>>b>>c;
        v[a].push_back({b,c});
    }
    for(int i=2;i<=n;++i)
        d[i]=INF;
    d[1]=0;
    x.push({1,0});
    while(!x.empty())
    {
        a=x.top().p;
        b=x.top().c;
        x.pop();
        if(b!=d[a])
            continue;
        c=v[a].size();
        for(int i=0;i<c;++i)
        {
            if(d[v[a][i].p]>b+v[a][i].c)
            {
                d[v[a][i].p]=b+v[a][i].c;
                x.push({v[a][i].p,d[v[a][i].p]});
            }
        }
    }
    for(int i=2;i<=n;++i)
        if(d[i]!=INF)
            so<<d[i]<<' ';
        else
            so<<0<<' ';
    return 0;
}