#include<fstream>
#include<vector>
#include<queue>
#define INF 999999999
#define mp make_pair
#define pb push_back
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int i,n,m,x,y,c,d[50100];
vector<pair<int,int> >l[50010];
struct cmp{
    bool operator()(int x,int y)
    {
        return d[x]>d[y];
    }

};
priority_queue<int,vector<int>,cmp>h;
int main()
{
    f>>n>>m;
    int yy;
    for(i=1;i<=m;++i)
    {
        f>>x>>yy>>c;
        l[x].pb(mp(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;
}