#include <bits/stdc++.h>
#define pii pair<int,int>
#define make_pii(a,b) make_pair(a,b)
#define INF -1

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

const int lmt = 5e4 + 1;
int n,m;
vector<pii> aList[lmt];

void citire()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y,c;
        fin>>x>>y>>c;
        aList[x].push_back(make_pii(y,c));
    }

}

void dijkstra(int src)
{
    set<pii> ndList;
    vector<int> dist(n+1,INF);
    dist[src]=0;
    ndList.insert(make_pii(0,src)); //pe first e distanta pana la nodul de pe pozitia second

    while(!ndList.empty())
    {
        pii currnt = *(ndList.begin());

        ndList.erase(ndList.begin());

        int cNod = currnt.second;

        vector<pii>::iterator i;
        for(i = aList[cNod].begin();i!=aList[cNod].end();++i)
        {
            int toNode = (*i).first;
            int weight = (*i).second;
            int newDist = dist[cNod] + weight;
            if(dist[toNode]==INF || dist[toNode] > newDist)
            {
                if(dist[toNode]!=INF)
                    ndList.erase(ndList.find(make_pii(dist[toNode],toNode)));

                dist[toNode] = newDist;
                ndList.insert(make_pii(dist[toNode],toNode));
            }
        }

    }

    for(int i=2;i<dist.size();++i)
        fout<<(dist[i] == INF ? 0 : dist[i])<<' ';
}

int main()
{
    citire();
    dijkstra(1);
    return 0;
}