#include <bits/stdc++.h>
using namespace std;
const int INFINIT=INT_MAX;
const int N=5e4+10;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector <pair<int,int>> a[N]; ///primu cost al doilea nod
int n;
bool sel[N];
int pred[N];
int d[N];
int main()
{
    int m;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        a[x].push_back({z,y});
    }
    for(int j=2;j<=n;j++)
    {
        d[j]=INFINIT;
    }
    d[1]=0;
    priority_queue <pair<int,int>> q;
    q.push({0,1});
    while(!q.empty())
    {
        int act=q.top().second;
        if(!sel[act])
        {
            sel[act]=true;
            for(int i=0;i<a[act].size();i++)
            {
                int y=a[act][i].second;
                int c=a[act][i].first;
                if((d[act]+c)<d[y])
                {
                    d[y]=d[act]+c;
                    pred[y]=act;
                    q.push({(-1)*d[y],y});
                }
            }
        }
        q.pop();
    }
    for(int i=2;i<=n;i++)
    {
        if(d[i]==INFINIT)
        g<<0<<" ";
        else
        g<<d[i]<<" ";
    }
    return 0;
}