#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

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

priority_queue<pair<int,int>> q;
vector<vector<pair<int,int>>> v;

int n,m;
int inf=10000000000;
int dist[50002];

int main()
{
    fin>>n>>m;
    int a,b,c;
    v.resize(n+1, vector<pair<int,int>>());
    for(int k=1;k<=m;k++)
    {
        fin>>a>>b>>c;
        v[a].push_back({b,c});
    }
    q.push({0,1});
    for(int k=2;k<=n;k++)
        dist[k]=inf;
    while(!q.empty())
    {
        pair p=q.top();
        q.pop();
        for(vector<pair<int,int>>:: iterator k=v[p.second].begin();k!=v[p.second].end();k++)
        {
             if(dist[k->first]>dist[p.second]+k->second)
             {
                 dist[k->first]=dist[p.second]+k->second;
                 q.push({dist[k->first],k->first});
             }
        }
    }
    for(int k=2;k<=n;k++)
    {
        if(dist[k]==inf)
            fout<<1<<" ";
        else
            fout<<dist[k]<<" ";
    }
    return 0;
}