#include <algorithm>
#include <vector>
#include <queue>
#include <fstream>
#define inf 2147483647
using namespace std;

struct nod
{
    int y;
    long long c;

    bool operator>(nod r)const
    {
        return c>r.c;
    }
};

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector<nod> G[50100];
int n,m;
long long cost[50010];
priority_queue <nod,vector<nod>,greater<nod> >q;
int viz[50010];

int main()
{
    int x,yo;
    long long co;
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        f>>x>>yo>>co;
        G[x].push_back({yo,co});
    }

    for(int i=1; i<=n; i++)
        cost[i]=inf;
    q.push({1,0});
    cost[1]=0;
    //viz[1]=1;
    while (!q.empty())
    {
        nod curent=q.top();
        viz[curent.y]=1;
       // while (!q.empty() && viz[q.top().y]==1)
          //  q.pop();
        for(int i=0; i<G[curent.y].size(); i++)
        {
            int vf=G[curent.y][i].y;
            if (cost[vf]>cost[curent.y]+G[curent.y][i].c)
            {
                cost[vf] =cost[curent.y]+G[curent.y][i].c;
                q.push({vf,cost[vf]});
            }
        }
    }
    for(int i=2; i<=n; ++i)
        if (cost[i]==inf)
            g<<"0 ";
        else
            g<<cost[i]<<" ";
    g<<"\n";
    return 0;
}