#include<fstream>
#include<vector>
#include<queue>
#define nmax 50002
#define INF 1000000000
using namespace std;
int n,m;
struct nod{int vecin; int cost;};
vector<nod> G[nmax];
vector<int> d(nmax,INF);
vector<int> v(nmax);
queue<int> c;
void citire()
{
    ifstream fin("dijkstra.in");
    int a,b,c;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        nod aux;
        aux.vecin=b;
        aux.cost=c;
        G[a].push_back(aux);
    }
}
void dijkstra(int x)
{
    d[x]=0;
    v[x]=1;
    c.push(x);
    while(!c.empty())
    {
        int crt=c.front();
        c.pop();
        for(int i=0;i<G[crt].size();i++)
        {

            if(d[G[crt][i].vecin]>d[crt]+G[crt][i].cost)
            {
                c.push(G[crt][i].vecin);
                d[G[crt][i].vecin]=d[crt]+G[crt][i].cost;
            }
        }
    }
}
void afisare()
{

    ofstream fout("dijkstra.out");
    for(int i=2;i<=n;i++)
        if(d[i]!=INF)
            fout<<d[i]<<" ";
        else
            fout<<"0 ";

}

int main()
{

    citire();
    dijkstra(1);
    afisare();
    return 0;
}