#include<fstream>
#include<vector>
#include<queue>
#define INF 999999999
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int i,m,n,x,yy,c,d[50010];
struct cmp
{
    bool operator()(int x,int y)
    {
        return d[x]>d[y];
    }
};
vector<pair<int,int> > l[50010];
priority_queue<int,vector<int>,cmp> h;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>yy>>c;
        l[x].push_back(make_pair(yy,c));
    }
    for(i=1;i<=n;++i)
    d[i]=INF;
    d[1]=0;
    h.push(1);
    pair<int,int> y;
    while(!h.empty())
    {
        x=h.top();
        h.pop();
        for(i=0;i<l[x].size();++i)
        {
            y=l[x][i];
            if(d[y.first]>d[x]+y.second)
            {
                d[y.first]=d[x]+y.second;
                h.push(y.first);
            }
        }
    }
    for(i=2;i<=n;++i)
    if(d[i]==INF)
    g<<"0 ";
    else
    g<<d[i]<<" ";
    g<<'\n';
    return 0;
}