#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=1000000000;
int dist[50002];

int main()
{
    fin>>n>>m;
    int tata,fiu;
    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())
    {
        tata=(q.top()).second;
        if(-(q.top()).first<=dist[tata])
        {
            q.pop();
            for(vector<pair<int,int>>:: iterator k=v[tata].begin();k!=v[tata].end();k++)
            {
                 fiu=k->first;
                 if(dist[fiu]>dist[tata]+k->second)
                 {
                     dist[fiu]=dist[tata]+k->second;
                     q.push({-dist[fiu],fiu});
                 }
            }
        }
        else
            q.pop();
    }
    for(int k=2;k<=n;k++)
    {
        if(dist[k]==inf)
            fout<<0<<" ";
        else
            fout<<dist[k]<<" ";
    }
    return 0;
}