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

using namespace std;

vector<vector<pair<int,int>>> ma;
priority_queue<pair<int,int>> q;
ifstream fin("dijkstra.in");
ofstream fout ("dijkstra.out");
vector<bool> vf;
vector<int> di;

int main()
{
    int n,m;
    fin>>n>>m;
    int x,y,c;
    ma.resize(n+1);
    vf.resize(n+1);
    di.resize(n+1,INT_MAX);
    for(int k=1;k<=m;k++)
    {
        fin>>x>>y>>c;
        ma[x].push_back({y,c});
    }
    q.push({0,1});
    di[1]=0;
    while(!q.empty())
    {
        if(vf[q.top().second]==1)
            continue;
        int a;
        a=q.top().second;
        vf[a]=true;
        q.pop();
        vector<pair<int,int>>::iterator el;
        for(el=ma[a].begin();el!=ma[a].end();el++)
        {
            if(!vf[(*el).first] && di[(*el).first]>di[a]+(*el).second)
            {
                di[(*el).first]=di[a]+(*el).second;
                q.push({-di[(*el).first],(*el).first});
            }
        }
    }
    for(int k=2;k<=n;k++)
    {
        if(vf[k]==1)
            fout<<di[k]<<" ";
        else
            fout<<0<<" ";
    }
    return 0;
}