#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

vector<pair<int,int>> muchii[50001];
priority_queue<pair<int,int>> pq;
int dist[100001];

int main()
{
    int n,m,a,b,c;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        muchii[a].push_back(make_pair(b,c));
    }
    pq.push(make_pair(0,1));
    dist[1]=0;
    for(int i=2;i<=n;i++)
        dist[i]=2e9;
    while(!pq.empty())
    {
        int nod=pq.top().second;
        if(-dist[nod]!=pq.top().first)
        {
            pq.pop();
            continue;
        }
        pq.pop();
        for(int i=0;i<muchii[nod].size();i++)
        {
            int urm=muchii[nod][i].first;
            int dis=muchii[nod][i].second;
            if(dist[nod]+dis<dist[urm])
            {
                dist[urm]=dist[nod]+dis;
                pq.push(make_pair(-dist[urm],urm));
            }
        }
    }
    for(int i=2;i<=n;i++)
        if(dist[i]==2e9)
            cout<<"0 ";
        else
            cout<<dist[i]<<' ';
    return 0;
}