#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

#define lim 50010
#define inf 100010

struct ini
{
    int ord,cost;
};
struct nod
{
    int cost,ord;

    bool operator < (const nod &other) const
    {
        return cost<other.cost;
    }
};
vector <ini> G[lim];
priority_queue <nod> q;
int n,m;
bool viz[lim];
int path[lim];


int main()
{
    int a,b,c;
    ini d;

    fin>>n>>m;
    for(int i=1; i<=m; i++)
        {
            fin>>a>>b>>c;
            G[a].push_back({b,c});
        }

    path[1]=0;
    for(int i=2; i<=n; i++)
        path[i]=inf;
    q.push({0,1});

    while(!q.empty())
    {
        nod aux=q.top();
        q.pop();

        if(viz[aux.ord])
            continue;
        viz[aux.ord]=true;

        for(auto it:G[aux.ord])
            if(path[aux.ord]+it.cost<path[it.ord])
            {
                path[it.ord]=path[aux.ord]+it.cost;
                q.push({-path[it.ord],it.ord});
            }

    }

    for(int i=2; i<=n; i++)
    {
        if(path[i]==inf)
            path[i]=0;
        fout<<path[i]<<' ';
    }


    fin.close();
    fout.close();
    return 0;
}