#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 0x3f3f3f3f

using namespace std;

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

struct drum
{
    int nod,dist;
    bool operator<(const drum &altu)const
    {
        return dist<altu.dist;
    }
};

vector <drum> G[50010];
priority_queue <drum> pq;
int d[50010],viz[50010],n,m;

void Dijkstra()
{
    for(int i=2;i<=n;i++)
        d[i]=inf;
    d[1]=0;
    drum dr;
    dr.nod=1;
    dr.dist=0;
    pq.push(dr);
    while(!pq.empty())
    {
        dr=pq.top();
        pq.pop();
        if(!viz[dr.nod])
        {
            viz[dr.nod]=1;
            for(int i=0;i<G[dr.nod].size();i++)
            {
                drum nou;
                nou.nod=G[dr.nod][i].nod;
                nou.dist=G[dr.nod][i].dist+d[dr.nod];
                if(!viz[nou.nod] && nou.dist<d[nou.nod])
                {
                    d[nou.nod]=nou.dist;
                    nou.dist=-nou.dist;
                    pq.push(nou);
                }
            }
        }
    }
    for(int i=2;i<=n;i++)
        if(d[i]==inf) g<<"0 ";
        else g<<d[i]<<' ';
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        drum nou;
        nou.nod=b;
        nou.dist=c;
        G[a].push_back(nou);
    }
    Dijkstra();
    f.close();
    g.close();
    return 0;
}