#include <bits/stdc++.h>
#define oo 1000000001
using namespace std;

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

int n,m,d[50005];
vector <pair<int,int>> l[50005];
bitset <50005> viz;
priority_queue <pair<int,int>> q;
// dijkstra

int main()
{
    int i,j,cost,k;
    fin>>n>>m;
    while(m--)
    {
        fin>>i>>j>>cost;
        l[i].push_back({j,cost});
    }
    q.push({0,1});
    d[1]=0;
    for(i=2;i<=n;i++)
        d[i]=oo;
    while(!q.empty())
    {
        k=q.top().second;
        q.pop();
        if(viz[k]==0)
        {
            viz[k]=1;
            for(auto e:l[k])
                if(d[e.first]>d[k]+e.second)
                {
                d[e.first]=d[k]+e.second;
                q.push({-d[e.first],e.first});
                }
        }
    }
    for(i=2;i<=n;i++)
        if(d[i]==oo)
            fout<<"0 ";
        else
            fout<<d[i]<<" ";
    return 0;
}