#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

#define NMAX 50002
#define inf 20000000

using namespace std;

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

struct nod{
    int v,c;
};

class cmp{
    public:
        bool operator()(nod A, nod B)
        {
            return A.c>B.c;
        }
};

int dist[NMAX],n,m;
vector <nod> graf[NMAX];
priority_queue <nod, vector<nod>, cmp> coada;
bitset <NMAX> viz;

void citire()
{
    int x,y,c;
    f>>n>>m;
    while(m--)
    {
        f>>x>>y>>c;
        graf[x].push_back({y,c});
    }
}

void init()
{
    int i;
    for(i=1;i<=n;i++)
        dist[i]=inf;
}

void dijkstra()
{
    while(!coada.empty())
    {
        int ns,ma,v,cost,lg,i;
        ns=coada.top().v;
        ma=coada.top().c;
        coada.pop();
        if(viz[ns]==0)
        {
            lg=graf[ns].size();
            for(i=0;i<lg;i++)
            {
                v=graf[ns][i].v;
                cost=graf[ns][i].c;
                if(dist[v]>ma+cost && viz[v]==0)
                {
                    dist[v]=ma+cost;
                    coada.push({v,dist[v]});
                }
            }
        }
        viz[ns]=1;
    }
}

void afisare()
{
    int i;
    for(i=2;i<=n;i++)
    {
        if(dist[i]==inf) dist[i]=0;
        g<<dist[i]<<" ";
    }
}
int main()
{
    citire();
    init();
    coada.push({1,0});
    dist[1]=0;
    dijkstra();
    afisare();
    f.close(); g.close();
    return 0;
}