#include <fstream>
#include <set>
#include <vector>
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
const int inf=0x3F3F3F3F;
class compare{
public:
    bool operator()(const pair<int,int> &a,const pair <int,int> &b)
    {
        return a.first<b.first;
    }
} ;
int n,m;
vector <pair <int,int> > G;
multiset <pair <int,int>,compare > heap;
vector <vector <pair<int,int> >  >L(50005);
vector <int> d(50005);
void read()
{
    fi>>n>>m;
    int x,y,c;
    for(int i=1; i<=m; i++)
    {
        fi>>x>>y>>c;
        L[x].push_back(make_pair(y,c));
    }
}
void dijkstra()
{
    for(int i=2; i<=n; i++) d[i]=inf;
    d[1]=0;
    heap.insert(make_pair(0,1));
    int  v,w;
    while(!heap.empty())
    {
        set<pair <int,int> >::iterator it;
        it=heap.begin();
        heap.erase(heap.begin());
        v=it->second;
        w=it->first;
        if(d[v]==w){
        for(int i=0; i<L[v].size();i++)
        {
            if(d[L[v][i].first]> w+L[v][i].second)
            {
                d[L[v][i].first]=w+L[v][i].second;
                heap.insert(make_pair(d[L[v][i].first],L[v][i].first));

            }
        }

    }}

    for(int i=2; i<=n; i++) {if(d[i]==inf) d[i]=0;fo<<d[i]<<" ";}
}
int main()
{
    read();
    dijkstra();
    return 0;
}