#include <cstdio>
#include <vector>
#include <utility>
#include <queue>
#include <functional>
#define NMAX 50001
#define INF 0x3f3f3f3f
using namespace std;

int n,m;
typedef struct pair <int,int> pereche;
vector < vector < pereche > > Graf;
priority_queue <int, vector <int>, greater <int> > Heap;
int dist[NMAX];

inline void read(){

    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int x,y,c;
    scanf("%d%d",&n,&m);
    Graf.resize(n+1);

    for(register int i=1;i<=m;++i){

        scanf("%d%d%d",&x,&y,&c);
        Graf[x].push_back(pereche(y,c));
    }
}

void Dijkstra(){

    for(register int i=1;i<=n;++i)
        dist[i] = INF;

    dist[1] = 0;
    Heap.push(1);
    int nod;
            while(!Heap.empty()){

                nod = Heap.top();
                Heap.pop();
                for(vector < pereche >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
                if(dist[it->first] > dist[nod] + it->second){

                    dist[it->first] = dist[nod] + it->second;
                    Heap.push(it->first);
                }

            }
}

inline void write(){

    for(register int i=2;i<=n;++i)
        if(dist[i] == INF)
            printf("%d ",0);
         else printf("%d ",dist[i]);
}

int main(){

    read();
    Dijkstra();
    write();

return 0;
}