#include <bits/stdc++.h>
#define Nmax 50001
#define INF 2e9+1
#define tip pair <int,int>
#define vec first
#define cost second
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
list <tip> G[Nmax];
int d[Nmax];
bitset <Nmax> inPQ;
struct cmp
{
    bool operator() (const int &x, const int &y) const
    {
        return d[x]<d[y];
    }
};
set <int,cmp> pq;
int main()
{
    int n,m,i,j,c,x;
    f>>n>>m;
    while(m--)
    {
        f>>i>>j>>c;
        G[i].push_back({j,c});
    }
    fill(d+2,d+n+1,INF);
    pq.insert(1);
    list <tip> :: iterator it;
    while(!pq.empty())
    {
        x=*pq.begin();
        pq.erase(pq.begin());
        inPQ[x]=false;
        for(it=G[x].begin();it!=G[x].end();it++)
            if(d[it->vec]>d[x]+it->cost)
            {
                d[it->vec]=d[x]+it->cost;
                if(!inPQ[it->vec])
                {
                    inPQ[it->vec]=true;
                    pq.insert(it->vec);
                }
            }
    }
    for(i=2;i<=n;i++)
    if(d[i]==INF) g<<0<<' ';
    else g<<d[i]<<' ';

    return 0;
}