#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int nmax = 50000;

const int INF = 1e9;

vector<pair<int,int>> v[nmax + 5];

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

int n,m;

int d[nmax + 5];

int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++) d[i] = INF;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        fin>>x>>y>>z;
        v[x].push_back({z,y});
    }
    d[1] = 0;
    q.push({0,1});
    while(!q.empty())
    {
        pair<int,int> fr = q.top();
        q.pop();
        if(fr.first != d[fr.second])
            continue;
        for(auto& i : v[fr.second])
        {
            if(fr.first + i.first < d[i.second])
                d[i.second] = fr.first + i.first,q.push({d[i.second],i.second});
        }
    }
    for(int i=2;i<=n;i++)
        fout<<(d[i]!=INF ? d[i] : 0)<<' ';
}