#include <bits/stdc++.h>

#define INF 1<<7
#define NM 50005

using namespace std;

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

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

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

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

void solve(int h)
{
    int nod,nnod,cost,x;
    for(int i=1;i<=n;++i)d[i]=INF;
    d[h]=0;
    inq[h]=1;
    q.push(h);
    while(!q.empty())
    {
        nod=q.top();
        q.pop();
        inq[nod]=0;
        for(size_t i=0;i<g[nod].size();++i)
        {
            nnod=g[nod].at(i).first,cost=g[nod].at(i).second;
            x=cost+d[nod];
            if(d[nnod]>x)
            {
                d[nnod]=x;
                if(inq[nnod]==false)
                {
                    inq[nnod]=1;
                    q.push(nnod);
                }
            }
        }
    }
}

int main()
{
    read();
    solve(1);
    for(int i=2;i<=n;++i)
        if(d[i]==INF)out<<0<<' ';
        else out<<d[i]<<' ';
    return 0;
}