#include <bits/stdc++.h>
#define N 50001
#define INF INT_MAX
using namespace std;

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

vector<pair<int,int>> v[N];
int d[N],n,m;
bool viz[N];

struct sort_
{
    bool operator()(int x,int y)
    {
        return d[x]>d[y];
    }
};
priority_queue<int,vector<int>,sort_> q;

int main()
{
    int i,a,b,ct,vf;
    
    fin>>n>>m;
    
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>ct;
        v[a].push_back(make_pair(b,ct));
    }
    
    for(i=1;i<=n;i++)
        d[i]=INF;
    d[1]=0;
    q.push(1);
    
    while(!q.empty())
    {
        vf=q.top();
        q.pop();
        
        if(!viz[vf])
        {
            viz[vf]=true;
            for(auto s:v[vf])
                if(d[vf]+s.second<d[s.first])
                {
                    viz[s.first]=false;
                    d[s.first]=d[vf]+s.second;
                    q.push(s.first);
                }
        }
    }
    
    for(i=2;i<=n;i++)
        if(d[i]==INF)
            fout<<"0 ";
        else
            fout<<d[i]<<" ";
    return 0;
}