#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define pb push_back
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
struct eee
{
    int nod,cost;
    bool operator <(const eee& a)const
    {
        return cost>a.cost;
    }
};
eee mp(int n,int c)
{
    eee t;
    t.nod=n;
    t.cost=c;
    return t;
}
int n,m,a,b,c,x,y,dist[50005];
vector <eee> v[50005];
priority_queue <eee> q;
int main()
{
    in>>n>>m;
    for(int i=2;i<=n;i++)dist[i]=1<<30;
    for(int i=1;i<=m;i++)
    {
        in>>a>>b>>c;
        v[a].pb(mp(b,c));
    }
    q.push(mp(1,0));
    while(!q.empty())
    {
        x=q.top().nod;
        y=q.top().cost;
        q.pop();
        if(y!=dist[x])continue;
        for(auto i:v[x])
        {
            if(dist[i.nod]>dist[x]+i.cost)
            {
                dist[i.nod]=dist[x]+i.cost;
                q.push(mp(i.nod,dist[i.nod]));
            }
        }
    }
    for(int i=2;i<=n;i++)
    {
        if(dist[i]==1<<30)dist[i]=0;
        out<<dist[i]<<' ';
    }
    return 0;
}