#include<queue>
#include<fstream>
#include<vector>
#define INF 0x3f3f3f
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> >v[50001];
int c[50010],N,M,d,x,y,z;

void dijkstra(int node)
{   c[node]=0;
    q.push(make_pair(node,0));
    while(!q.empty())
            {
               int asdf=q.top().first;
               q.pop();
               for(int i=0;i<v[asdf].size();i++)
                    if(c[v[asdf][i].first]>c[asdf]+v[asdf][i].second)
                           {
                               c[v[asdf][i].first]=c[asdf]+v[asdf][i].second;
                               q.push(make_pair(v[asdf][i].first,c[v[asdf][i].first]));
                           }
            }
}

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

    return 0;
}