#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int use[50010],best[50010];
const int maxn=(1<<30);
struct st
{
    int nod, cost;
};
struct comp
{
    bool operator () (st x, st y)
    {
    return x.cost>y.cost;
    }
};

priority_queue <st, vector<st>, comp> q;
vector <int> a[50010],c[50010];
int n,m;

void DJK (int node)
{
    int i,nod2;
st aux,aux2;
best[1]=0;
aux.nod=1;
aux.cost=0;
q.push(aux);
while (!q.empty())
{
    aux=q.top();
    q.pop();

       // use[aux.nod]=1;
        for (i=0;i<a[aux.nod].size();i++)
        {
            nod2=a[aux.nod][i];
            if (best[nod2]>best[aux.nod]+c[aux.nod][i])
            {
                best[nod2]=best[aux.nod]+c[aux.nod][i];
                aux2.nod=nod2;
                aux2.cost=best[nod2];
                q.push(aux2);
            }
        }

}
}


int main()
{
    int i,x;
    st aux;
f>>n>>m;
for (i=1;i<=m;i++)
{
    f>>x>>aux.nod>>aux.cost;
    a[x].push_back(aux.nod);
    c[x].push_back(aux.cost);

}
for (i=1;i<=n;i++)
{
    best[i]=maxn;
}
best[i]=0;
DJK(1);
for (i=2;i<=n;i++)
{
    if (best[i]==maxn) g<<"0 ";
    else g<<best[i]<<" ";
}
    return 0;
}