#include <fstream>
#include<deque>
#include<climits>
#include<vector>
#include<queue>
FILE*f;
FILE*k;
using namespace std;
deque<pair<int,int>>g[50001];
int i,j,m,n,x,y,z,all,al,d[50001];
struct compara{
bool operator()(int x,int y)
{
    return d[x]>d[y];
}
};
priority_queue<int,vector<int>,compara>coada;
int main()
{f=fopen("dijksta.in","r");
k=fopen("dijkstra.out","w");
fscanf(f,"%d%d",&n,&m);

    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&z);
        g[x].push_back(make_pair(y,z));
    }
    for(i=2;i<=n;i++)
        d[i]=250000;
    d[1]=0;
    coada.push(1);
    while(!coada.empty())
    {
        al=coada.top();
        coada.pop();
        while(!g[al].empty())
        {if(d[g[al].front().first]>d[al]+g[al].front().second)
            {d[g[al].front().first]=min(d[g[al].front().first],d[al]+g[al].front().second);
            all=g[al].front().first;
            g[al].pop_front();
            coada.push(all);
        }else{g[al].pop_front();}
    }
    }
    for(i=2;i<=n;i++)
        fprintf(k,"%d ",d[i]);
    return 0;
}