#include <bits/stdc++.h>
#define Nmax 50005
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int n, m, x, y, c, i, d[Nmax];
struct muchie
{
    int y, c;
};
struct cmp
{
    bool operator()(int x, int y)
    {
        if(d[x]!=d[y])
            return d[x]<d[y];
        return x<y;
    }
};
vector <muchie> v[Nmax];
set <int, cmp> s;
int main()
{
    fin >> n >> m;
    for(i=1; i<=m; i++)
    {
        fin >> x >> y >> c;
        v[x].push_back({y, c});
    }
    for(i=2; i<=n; i++)
        d[i]=INT_MAX;
    for(i=1;i<=n;i++)
        s.insert(i);
    while(!s.empty())
    {
        set <int, cmp> :: iterator it;
        it=s.begin();
        x=*it;
        s.erase(it);
        if(d[x]==INT_MAX)
            break;
        for(i=0; i<v[x].size(); i++)
            if(d[v[x][i].y]>d[x]+v[x][i].c)
            {
                int aux=v[x][i].y;
                d[v[x][i].y]=d[x]+v[x][i].c;
                if(s.find(v[x][i].y)!=s.end())
                    s.erase(s.find(v[x][i].y));
                s.insert(v[x][i].y);
            }
    }
    for(i=2; i<=n; i++)
    {
        if(d[i]==INT_MAX)
            fout << 0 << ' ';
        else
            fout << d[i] << ' ';
    }
    return 0;
}