#include<queue>
#include<fstream>
#include<vector>
#define oo 1000000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct compare{
   bool operator()(pair<int,int> p1, pair<int,int> p2){
        return p1.second>p2.second;
   }
};

priority_queue< pair<int,int> , vector< pair<int,int> > , compare >q;
vector< pair<int,int> >a[50001];
int d[50001],N,M,x,y,z;

void dijkstra()
{   d[1]=0;
    q.push(make_pair(1,0));
    while(!q.empty())
            {
               int varf=q.top().first;
               q.pop();
               for(int i=0;i<a[varf].size();i++)
                    if(d[a[varf][i].first]>d[varf]+a[varf][i].second)
                           {
                               d[a[varf][i].first]=d[varf]+a[varf][i].second;
                               q.push(make_pair(a[varf][i].first,d[a[varf][i].first]));
                           }
            }
}

int main()
{
    fin>>N>>M;
    for(int i=2;i<=N;i++)
        d[i]=oo;
    for(int i=1;i<=M;i++)
    {
        fin>>x>>y>>z;
        a[x].push_back(make_pair(y,z));
    }
    dijkstra();
    for(int i=2;i<=N;i++)
        if(d[i]==oo)
        fout<<"0"<<' ';
    else fout <<d[i]<<' ';

    return 0;
}