#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int inf=2000000000;
int n,m,p,x,y,c,nod,cost,i,d[50002];
vector <pair<int,int>> graf[50002];
typedef pair <int,int> per;
priority_queue <per, vector<per>, greater<per> > q;



int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        graf[x].push_back(make_pair(y,c));
    }
    p=1;///nodul de start
    for(i=1;i<=n;i++)
        if(i!=p)
            d[i]=inf;
    q.push(make_pair(p,d[p]));
    while(q.size())
    {
        nod=q.top().first;
        cost=q.top().second;
        q.pop();
        if(d[nod]!=cost)
            continue;
        for(auto x:graf[nod])
        {
            if(d[x.first]>cost+x.second)
            {
                d[x.first]=cost+x.second;
                q.push(make_pair(x.first,d[x.first]));
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        if(d[i]==inf)
            fout<<0<<' ';
        else
            fout<<d[i]<<' ';
    }
    return 0;
}