#include <bits/stdc++.h>

using namespace std;

const int NM=50005,oo=1<<30;

ifstream in ("dijkstra.in");
ofstream out("dijkstra.out");

int d[NM],n,m;
bool inq[NM];

vector <pair<int,int> > p[NM];
struct cmp
{
    bool operator()(int x,int y)
    {
        return (d[x]<d[y]);
    }
};
priority_queue <int,vector<int>,cmp>q;

void read()
{
    int i,j,c;
    in>>n>>m;
    for(int g=0;g<m;++g)
    {
        in>>i>>j>>c;
        p[i].push_back(make_pair(j,c));
    }
}

void print()
{
    for(int i=2;i<=n;++i)
        if(d[i]!=oo)out<<d[i]<<" ";
        else out<<"0 ";
}

void solve(int y)
{
    int nod,cost,nnod,ax,siz;
    for(int i=1;i<=n;++i)
        d[i]=oo;
    d[y]=0;
    q.push(y);
    inq[y]=1;
    while(!q.empty())
    {
        nod=q.top();
        q.pop();
        inq[nod]=0;
        siz=p[nod].size();
        for(int i=0;i<siz;++i)
        {
            nnod=p[nod].at(i).first,cost=p[nod].at(i).second;
            ax=cost+d[nod];
            if(d[nnod]>ax)
            {
                d[nnod]=ax;
                if(!inq[nnod])
                {
                    inq[nnod]=1;
                    q.push(nnod);
                }
            }
        }
    }
}

int main()
{
    read();
    solve(1);
    print();
    return 0;
}