#include <fstream>
#include <climits>
#include <set>
#include <vector>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,m,dist[50003];

vector<pair<int,int> >g[50003];

multiset<pair<int,int> >heap;

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        g[x].push_back(make_pair(y,c));
    }
    for(int i=2;i<=n;i++)
        dist[i]=INT_MAX;
    heap.insert(make_pair(0,1));
    while(!heap.empty())
        {
            int nod=heap.begin()->second;
            int d=heap.begin()->first;
            heap.erase(heap.begin());
            for(vector<pair<int,int> > :: iterator it=g[nod].begin();it!=g[nod].end();it++)
            {
                int to=it->first;
                int cost=it->second;
                if(dist[to]>dist[nod]+cost)
                {
                    if(dist[to]!=INT_MAX)
                        heap.erase(heap.find(make_pair(dist[to],to)));
                    dist[to]=dist[nod]+cost;
                    heap.insert(make_pair(dist[to],to));
                }

            }
        }
    for(int i=2;i<=n;i++)
    {
        if(dist[i]==INT_MAX)
            dist[i]=0;
        fout<<dist[i]<<" ";
    }

}