#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define N 50010
#define INF 20000001

using namespace std;

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

vector<pair<int,int>> vec[N];
bool Queue[N];
int dist[N],i,j,n,m,k,t,p,r;

int main()
{
    int from,to,cost,ok;
        ok=1;
        f>>n>>m;
        while(m!=0)
        {
            f>>from>>to>>cost;
            vec[from].push_back(make_pair(to,cost));
            m--;
        }
        for(i=1;i<=n;i++)
            dist[i]=INF;
        dist[1]=0;
        queue<int> q;
        q.push(1);
        Queue[1]=true;
        int nod;
        while(!q.empty())
        {
            nod=q.front();
            Queue[nod]=false;
            q.pop();
            for(vector<pair<int,int>>::iterator it=vec[nod].begin();it!=vec[nod].end();++it)
            {
                int to=it->first;
                int cost=it->second;
                if(dist[to]>dist[nod]+cost)
                {
                    dist[to]=dist[nod]+cost;
                    if(!Queue[to])
                    {
                        Queue[to]=true;
                        q.push(to);
                    }
                }
            }
        }
        for(i=2;i<=n;i++)
        {
            if(dist[i]==INF)
                g<<0<<' ';
            else
                g<<dist[i]<<' ';
        }
}