#include <fstream>
#include <vector>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,d[50100],sel[50100],k,i,x,y,cost;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector <pair <int,int> > G[50100];
priority_queue <pair <int,int> ,vector <pair <int,int> > ,greater < pair <int,int> > > Q;

void djk(int p)
{
    for (auto i: G[p]) {
        Q.push(i);
        d[i.second]=i.first;
    }
    sel[p]=true;
    while (!Q.empty())
    {
        while (!Q.empty()&&sel[Q.top().second])
            Q.pop();
        if (!Q.empty())
        {
            k=Q.top().second;
            sel[k]=true;
            Q.pop();
            for (auto i: G[k])
                if (d[i.second]>d[k]+i.first)
            {
                d[i.second]=d[k]+i.first;
                Q.push(i);
            }
        }
    }
}
int main()
{
        in>>n>>m;
        for (i=1;i<=m;++i)
        {
            in>>x>>y>>cost;
            G[x].push_back({cost,y});
        }
        for (i=2;i<=n;++i)
            d[i]=inf;
        djk(1);
        for (i=2;i<=n;++i)
        {
            if (d[i]==inf) out<<0;
            else out<<d[i];
            out<<" ";
        }
    return 0;
}