#include<fstream>
#include<algorithm>
#include<queue>
#include<list>
using namespace std;
#define INF 1<<30
#define MAXSIZE 50001
#define cost first
#define poz second
vector<int> dist(MAXSIZE,INF);
int from,to,costul,n,m,i;
list< pair<int,int> > graph[MAXSIZE];
priority_queue< pair<int,int>,vector< pair<int,int> >,greater< pair<int,int> > > myHeap;

void dijkstra(int);
inline bool isInf(int number) { return (number == INF); };

int main()
{
    ifstream in("dijkstra.in");
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>from>>to>>costul;
        graph[from].push_back(make_pair(costul,to));
    }
    in.close();
    dijkstra(1);

    ofstream out("dijkstra.out");
    for(i=2;i<=n;i++)
        out<<(dist[i]==INF ? 0:dist[i])<<" ";
    out.close();
    return 0;
}

void dijkstra(int StartNode)
{
    dist[StartNode]=0;
    pair<int,int> CurrentNode;
    list< pair<int,int> >::iterator vecin;
    myHeap.push(make_pair(0,StartNode));
    list< pair<int,int> >::iterator end;
    while(!myHeap.empty())
    {
        CurrentNode=myHeap.top();
        myHeap.pop();
        end=graph[CurrentNode.poz].end();
        for(vecin=graph[CurrentNode.poz].begin();vecin!=end;++vecin)
            if(dist[vecin->poz]>dist[CurrentNode.poz]+vecin->cost)
            {
                dist[vecin->poz]=dist[CurrentNode.poz]+vecin->cost;
                myHeap.push(make_pair(dist[vecin->poz],vecin->poz));
            }
    }
}